short_path_gives_linkage_four_strong
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.
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.
classical obtain ⟨-, hstrong'⟩ := hstrongThe 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.
uses
List.toFinset_card_of_noduphave 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
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`.
have hmem_s₂ : s₂ ∉ p₁.toFinset := by simpa using hp₁avoid.1 have hmem_t₂ : t₂ ∉ p₁.toFinset := by simpa using hp₁avoid.2
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.
have hst : s₂ ≠ t₂ := by intro hh rw [hh] at hnodup simp at hnodup
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.
obtain ⟨p₂, hp₂path, hp₂avoid⟩ := hstrong' p₁.toFinset hscard s₂ t₂ hmem_s₂ hmem_t₂ hstThe 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₂.
uses
Or.inlrefine ⟨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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)