AFTD Auto-Formalizing Theoretical Domains

digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_right

theoremverified

Let D be a 4-strong semicomplete multipartite digraph. If s₁, t₁, s₂, t₂ are pairwise distinct vertices such that there is an arc between s₂ and t₂ in either direction, then there exist vertex-disjoint directed paths p₁ and p₂ linking {s₁, t₁} and {s₂, t₂} unilaterally.

Statement

theorem digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_right
    {V : Type*} [Fintype V] (D : Digraph V)
    (hstrong : digraph_is_k_strong D 4)
    (hmulti : digraph_is_semicomplete_multipartite D)
    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)
    (hadj : D.Adj s₂ t₂ ∨ D.Adj t₂ s₂) :
    ∃ (p₁ p₂ : List V),
      (digraph_is_directed_path D p₁ s₁ t₁ ∨ digraph_is_directed_path D p₁ t₁ s₁) ∧
      (digraph_is_directed_path D p₂ s₂ t₂ ∨ digraph_is_directed_path D p₂ t₂ s₂) ∧
      p₁.Disjoint p₂
Source
step towards op_620_four_strong_semicomplete_multipartite_unilaterally_two_linked
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof reduces the claim to the previously proved theorem where the first terminal pair is adjacent (`digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked`). By swapping the roles of the terminal pairs (s₁, t₁) and (s₂, t₂), the adjacency hypothesis on {s₂, t₂} becomes an adjacency condition on the first pair. The resulting disjoint paths are then swapped to produce the desired unilateral 2-linkage for the original pairs.

  1. The permuted list of terminals [s₂, t₂, s₁, t₁] contains no duplicate vertices

    Unfolding the definitions of list membership and duplicates reduces the assumption that [s₁, t₁, s₂, t₂] has distinct elements to the conjunction of all pairwise disequalities among s₁, t₁, s₂, and t₂. Propositional tautology reasoning then establishes that the reordered list [s₂, t₂, s₁, t₁] likewise has distinct elements.

    lines 12–18

    uses List.nodup_cons, List.mem_cons, List.not_mem_nil, or_false, not_or, List.nodup_nil, and_true

      have hnodup' : [s₂, t₂, s₁, t₁].Nodup := by
        have h' := hnodup
        simp only [List.nodup_cons] at h'
        simp only [List.mem_cons, List.not_mem_nil, or_false, not_or, List.nodup_nil, and_true] at h'
        simp only [List.nodup_cons]
        simp only [List.mem_cons, List.not_mem_nil, or_false, not_or, List.nodup_nil, and_true]
        tauto
  2. There exist vertex-disjoint directed paths q₁ and q₂ unilaterally linking {s₂, t₂} and {s₁, t₁}, respectively

    Applying the theorem `digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked` with the pairs swapped—using (s₂, t₂) as the first terminal pair and (s₁, t₁) as the second—produces paths q₁ and q₂ since s₂ and t₂ are assumed to be adjacent.

    lines 19–20

    uses digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked

      obtain ⟨q₁, q₂, hq₁, hq₂, hdisj⟩ :=
        digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked D hstrong hmulti hnodup' hadj
  3. There exist vertex-disjoint directed paths p₁ and p₂ unilaterally linking {s₁, t₁} and {s₂, t₂}, respectively

    Setting p₁ = q₂ and p₂ = q₁ provides the required paths: p₁ unilaterally links {s₁, t₁}, p₂ unilaterally links {s₂, t₂}, and their vertex-disjointness follows from the symmetry of list disjointness.

    line 21

      exact ⟨q₂, q₁, hq₂, hq₁, hdisj.symm⟩
List.nodup_cons
a list `a :: l` has no duplicate elements if and only if `a ∉ l` and `l` has no duplicates
List.mem_cons
an element `a` belongs to `b :: l` if and only if `a = b` or `a ∈ l`
List.not_mem_nil
the empty list has no elements
or_false
for any proposition P, `P ∨ False` is equivalent to `P`
not_or
negation of a disjunction: `¬(P ∨ Q)` is equivalent to `¬P ∧ ¬Q`
List.nodup_nil
the empty list has no duplicate elements
and_true
for any proposition P, `P ∧ True` is equivalent to `P`
digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked
in a 4-strong semicomplete multipartite digraph, if the first pair of distinct terminals is adjacent in either direction, then there exist vertex-disjoint directed paths unilaterally linking the two pairs

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- In a 4-strong semicomplete multipartite digraph, if the second terminal pair is adjacent, unilateral 2-linkage exists. -/theorem digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_right    {V : Type*} [Fintype V] (D : Digraph V)    (hstrong : digraph_is_k_strong D 4)    (hmulti : digraph_is_semicomplete_multipartite D)    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)    (hadj : D.Adj s₂ t₂ ∨ D.Adj t₂ s₂) :    ∃ (p₁ p₂ : List V),      (digraph_is_directed_path D p₁ s₁ t₁ ∨ digraph_is_directed_path D p₁ t₁ s₁) ∧      (digraph_is_directed_path D p₂ s₂ t₂ ∨ digraph_is_directed_path D p₂ t₂ s₂) ∧      p₁.Disjoint p₂ := by  have hnodup' : [s₂, t₂, s₁, t₁].Nodup := by    have h' := hnodup    simp only [List.nodup_cons] at h'    simp only [List.mem_cons, List.not_mem_nil, or_false, not_or, List.nodup_nil, and_true] at h'    simp only [List.nodup_cons]    simp only [List.mem_cons, List.not_mem_nil, or_false, not_or, List.nodup_nil, and_true]    tauto  obtain ⟨q₁, q₂, hq₁, hq₂, hdisj⟩ :=    digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked D hstrong hmulti hnodup' hadj  exact ⟨q₂, q₁, hq₂, hq₁, hdisj.symm⟩
See it in the graphDiscuss this resultChallenge it