AFTD Auto-Formalizing Theoretical Domains

short_path_gives_linkage_four_strong

theoremverified

In a 4-strong digraph D, if there is a directed path between {s₁, t₁} with at most 3 vertices that avoids {s₂, t₂}, then there exist vertex-disjoint directed paths unilaterally linking {s₁, t₁} and {s₂, t₂}.

Statement

theorem short_path_gives_linkage_four_strong
    {V : Type*} [Fintype V] (D : Digraph V)
    (hstrong : digraph_is_k_strong D 4)
    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)
    (p₁ : List V)
    (hp₁path : digraph_is_directed_path D p₁ s₁ t₁ ∨ digraph_is_directed_path D p₁ t₁ s₁)
    (hp₁len : p₁.length ≤ 3)
    (hp₁avoid : s₂ ∉ p₁ ∧ t₂ ∉ p₁) :
    ∃ (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 2
  • digraph_is_k_strongA finite digraph D is k-strong (k-strongly connected) if its vertex count exceeds k and for every vertex subset s of cardinality strictly…
  • digraph_is_directed_pathA directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u…
Used by 1
  • linkage_of_common_neighborIn a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₁ → v → t₁) or (t₁ → v → s₁), then unilateral 2-linkage exists for {s₁,…

The proof, explained

Since the given directed path p₁ between {s₁, t₁} has at most 3 vertices and no duplicates, its vertex set has size at most 3. By 4-strong connectivity, removing fewer than 4 vertices cannot disconnect the digraph, so there exists a directed path p₂ from s₂ to t₂ that avoids every vertex of p₁. The pair (p₁, p₂) then forms the desired vertex-disjoint unilateral 2-linkage.

  1. Extract the vertex-avoiding path property from 4-strongness

    Enable classical logic and unpack the definition of 4-strong connectivity (`digraph_is_k_strong D 4`) to obtain the property `hstrong'`: between any two distinct vertices not belonging to a subset s of fewer than 4 vertices, there is a directed path completely avoiding s.

    lines 14–15

      classical
      obtain ⟨-, hstrong'⟩ := hstrong
  2. The vertex set of p₁ has cardinality strictly less than 4

    Because p₁ is a directed path, its vertices contain no duplicates (`p₁.Nodup`). Converting the list p₁ to a finite set preserves size via `List.toFinset_card_of_nodup`, so |p₁.toFinset| = p₁.length ≤ 3 < 4.

    lines 16–19

    uses List.toFinset_card_of_nodup

      have hp₁nodup : p₁.Nodup := hp₁path.elim (fun h => h.2.1) (fun h => h.2.1)
      have hscard : p₁.toFinset.card < 4 := by
        rw [List.toFinset_card_of_nodup hp₁nodup]
        omega
  3. The terminals s₂ and t₂ do not lie on p₁

    The hypothesis `hp₁avoid` asserts s₂ ∉ p₁ and t₂ ∉ p₁, which immediately translates to s₂ and t₂ not belonging to the finite set `p₁.toFinset`.

    lines 20–21

      have hmem_s₂ : s₂ ∉ p₁.toFinset := by simpa using hp₁avoid.1
      have hmem_t₂ : t₂ ∉ p₁.toFinset := by simpa using hp₁avoid.2
  4. The terminals s₂ and t₂ are distinct

    Suppose s₂ = t₂. Substituting this equality into the assumption that [s₁, t₁, s₂, t₂] has no duplicate elements yields a list with repeated elements, which is a contradiction.

    lines 22–25

      have hst : s₂ ≠ t₂ := by
        intro hh
        rw [hh] at hnodup
        simp at hnodup
  5. There is a directed path p₂ from s₂ to t₂ avoiding all vertices of p₁

    Apply the 4-strong connectivity property `hstrong'` with avoiding set s = p₁.toFinset (which has size < 4) and distinct endpoints s₂, t₂ ∉ p₁.toFinset. This yields a directed path p₂ from s₂ to t₂ whose vertices are disjoint from p₁.toFinset.

    line 26

      obtain ⟨p₂, hp₂path, hp₂avoid⟩ := hstrong' p₁.toFinset hscard s₂ t₂ hmem_s₂ hmem_t₂ hst
  6. The paths p₁ and p₂ form the required vertex-disjoint unilateral 2-linkage

    Supply p₁ and p₂ as witnesses: p₁ unilaterally links {s₁, t₁} by hypothesis, p₂ provides a directed path from s₂ to t₂ (giving unilateral linkage via `Or.inl`), and any shared vertex would belong to both p₂ and p₁.toFinset, contradicting the avoidance property of p₂.

    lines 27–29

    uses Or.inl

      refine ⟨p₁, p₂, hp₁path, Or.inl hp₂path, ?_⟩
      intro a ha hb
      exact hp₂avoid a hb (by simpa using ha)
List.toFinset_card_of_nodup
If a list has no duplicate elements, the cardinality of the finite set of its elements equals the length of the list.
Or.inl
Constructs a proof of a disjunction A ∨ B given a proof of the left disjunct A.

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

/-- If there is a short directed path (at most 3 vertices) between one terminal pair avoiding the other, 4-strongness gives unilateral 2-linkage. -/theorem short_path_gives_linkage_four_strong    {V : Type*} [Fintype V] (D : Digraph V)    (hstrong : digraph_is_k_strong D 4)    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)    (p₁ : List V)    (hp₁path : digraph_is_directed_path D p₁ s₁ t₁ ∨ digraph_is_directed_path D p₁ t₁ s₁)    (hp₁len : p₁.length ≤ 3)    (hp₁avoid : s₂ ∉ p₁ ∧ t₂ ∉ p₁) :    ∃ (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  classical  obtain ⟨-, hstrong'⟩ := hstrong  have hp₁nodup : p₁.Nodup := hp₁path.elim (fun h => h.2.1) (fun h => h.2.1)  have hscard : p₁.toFinset.card < 4 := by    rw [List.toFinset_card_of_nodup hp₁nodup]    omega  have hmem_s₂ : s₂ ∉ p₁.toFinset := by simpa using hp₁avoid.1  have hmem_t₂ : t₂ ∉ p₁.toFinset := by simpa using hp₁avoid.2  have hst : s₂ ≠ t₂ := by    intro hh    rw [hh] at hnodup    simp at hnodup  obtain ⟨p₂, hp₂path, hp₂avoid⟩ := hstrong' p₁.toFinset hscard s₂ t₂ hmem_s₂ hmem_t₂ hst  refine ⟨p₁, p₂, hp₁path, Or.inl hp₂path, ?_⟩  intro a ha hb  exact hp₂avoid a hb (by simpa using ha)
See it in the graphDiscuss this resultChallenge it