digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked
Let D be a 4-strong semicomplete multipartite digraph on a finite type V. If s₁, t₁, s₂, t₂ are pairwise distinct vertices of D such that there is an arc between s₁ and t₁ in either direction, then there exist vertex-disjoint directed paths p₁ and p₂ where p₁ connects {s₁, t₁} and p₂ connects {s₂, t₂} in either direction.
Statement
theorem digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked {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₂
- Related work
- arXiv:2610.36895 Sec. 5
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_semicomplete_multipartiteA digraph D is semicomplete multipartite if it is loopless and its underlying inclusive simple graph has transitive non-adjacency (i.e.,…
- 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
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_rightLet D be a 4-strong semicomplete multipartite digraph. If s₁, t₁, s₂, t₂ are pairwise distinct vertices such that there is an arc between…
Read back from the Lean
Let V be a finite type and D be a directed graph on V. Assume:
1. D is 4-strongly connected (digraph_is_k_strong D 4).
2. D is semicomplete multipartite (digraph_is_semicomplete_multipartite D).
3. s₁, t₁, s₂, t₂ are pairwise distinct vertices in V ([s₁, t₁, s₂, t₂].Nodup).
4. s₁ and t₁ are adjacent in D in at least one direction (D.Adj s₁ t₁ ∨ D.Adj t₁ s₁).
Then there exist lists of vertices p₁ and p₂ in V such that:
1. p₁ is a simple directed path in D either from s₁ to t₁ or from t₁ to s₁,
2. p₂ is a simple directed path in D either from s₂ to t₂ or from t₂ to s₂, and
3. p₁ and p₂ are vertex-disjoint (p₁.Disjoint p₂).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Because s₁ and t₁ are adjacent, the single arc between them already forms a 2-vertex directed path p₁ connecting {s₁, t₁}. In a 4-strong digraph, deleting fewer than 4 vertices preserves strong connectivity; hence deleting the 2-element set {s₁, t₁} leaves a directed path p₂ between s₂ and t₂. By construction, p₂ completely avoids {s₁, t₁}, which immediately guarantees that p₁ and p₂ are vertex-disjoint.
The four terminal vertices s₁, t₁, s₂, t₂ are pairwise distinct.
Because the list [s₁, t₁, s₂, t₂] contains no duplicates by assumption, equating any pair among them produces an immediate contradiction. Each pairwise inequality (s₁ ≠ t₁, s₂ ≠ s₁, s₂ ≠ t₁, t₂ ≠ s₁, t₂ ≠ t₁, and s₂ ≠ t₂) is established by assuming equality and simplifying the no-duplicates hypothesis.
classical have h11 : s₁ ≠ t₁ := by intro heq simp [heq] at hnodup have h21 : s₂ ≠ s₁ := by intro heq subst s₂ simp at hnodup have h2t1 : s₂ ≠ t₁ := by intro heq subst s₂ simp at hnodup have h3s1 : t₂ ≠ s₁ := by intro heq subst t₂ simp at hnodup have h3t1 : t₂ ≠ t₁ := by intro heq subst t₂ simp at hnodup have h22 : s₂ ≠ t₂ := by intro heq subst s₂ simp at hnodup
The obstacle set s = {s₁, t₁} has cardinality 2 < 4, and neither s₂ nor t₂ belongs to s.
Since s₁ ≠ t₁, the finset s = {s₁, t₁} has cardinality 2 by Finset.card_pair, so |s| < 4. Furthermore, by expanding set membership with Finset.mem_insert, Finset.mem_singleton, and not_or, s₂ ∉ s and t₂ ∉ s follow from the distinctness of the terminals.
uses
Finset.card_pair,Finset.mem_insert,Finset.mem_singleton,not_orlet s : Finset V := {s₁, t₁} have hcard : s.card < 4 := by have hc : s.card = 2 := by dsimp [s] exact Finset.card_pair h11 omega have hs2 : s₂ ∉ s := by simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨h21, h2t1⟩ have ht2 : t₂ ∉ s := by simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨h3s1, h3t1⟩
There exists a directed path p₂ from s₂ to t₂ avoiding all vertices of s = {s₁, t₁}.
By definition of a 4-strong digraph, removing any subset of strictly fewer than 4 vertices leaves a directed path between any two remaining distinct vertices. Applying this to the 2-element set s = {s₁, t₁} and the vertices s₂, t₂ ∉ s with s₂ ≠ t₂ yields a directed path p₂ from s₂ to t₂ whose vertices are all disjoint from s.
obtain ⟨p₂, hp₂path, hp₂avoid⟩ := hstrong.2 s hcard s₂ t₂ hs2 ht2 h22Any directed arc between distinct vertices forms a 2-vertex directed path.
If there is an arc from u to v, then u ≠ v because semicomplete multipartite digraphs have no self-loops. Unfolding the definition of a directed path, the list [u, v] has distinct vertices, starts at u, ends at v, and consists of the single valid directed step u → v.
have path_of_adj : ∀ {u v : V}, D.Adj u v → digraph_is_directed_path D [u, v] u v := by intro u v huv have hne : u ≠ v := by rintro rfl exact hmulti.1 u huv unfold digraph_is_directed_path simp [huv, hne]
Both s₁ and t₁ belong to s.
By definition of the set s = {s₁, t₁}, both endpoints s₁ and t₁ are members of s.
have hs1mem : s₁ ∈ s := by simp [s] have ht1mem : t₁ ∈ s := by simp [s]
If there is an arc from s₁ to t₁, the paths p₁ = [s₁, t₁] and p₂ are vertex-disjoint directed paths connecting the respective pairs.
In the forward case where D.Adj s₁ t₁, the 2-vertex list p₁ = [s₁, t₁] is a directed path from s₁ to t₁. Any vertex in p₁ is either s₁ or t₁, both of which belong to s; since p₂ was constructed to avoid every element of s, no vertex of p₁ can appear in p₂, ensuring that p₁ and p₂ are disjoint.
uses
Or.inl,List.mem_cons,List.not_mem_nil,or_falsercases hadj with hst | hts · refine ⟨[s₁, t₁], p₂, Or.inl (path_of_adj hst), Or.inl hp₂path, ?_⟩ intro a ha hb simp only [List.mem_cons, List.not_mem_nil, or_false] at ha rcases ha with h | h · rw [h] at hb exact (hp₂avoid s₁ hb) hs1mem · rw [h] at hb exact (hp₂avoid t₁ hb) ht1mem
If there is an arc from t₁ to s₁, the paths p₁ = [t₁, s₁] and p₂ are vertex-disjoint directed paths connecting the respective pairs.
Symmetrically, in the reverse case where D.Adj t₁ s₁, p₁ = [t₁, s₁] is a directed path from t₁ to s₁. Its vertices t₁ and s₁ are members of s, so disjointness with p₂ again follows from p₂ avoiding all vertices of s.
uses
Or.inr,Or.inl,List.mem_cons,List.not_mem_nil,or_false· refine ⟨[t₁, s₁], p₂, Or.inr (path_of_adj hts), Or.inl hp₂path, ?_⟩ intro a ha hb simp only [List.mem_cons, List.not_mem_nil, or_false] at ha rcases ha with h | h · rw [h] at hb exact (hp₂avoid t₁ hb) ht1mem · rw [h] at hb exact (hp₂avoid s₁ hb) hs1mem
Finset.card_pair- A finite set consisting of two distinct elements has cardinality 2.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
not_or- The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q (De Morgan's law).
Or.inl- Constructs a proof of a disjunction a ∨ b from a proof of the left disjunct a.
Or.inr- Constructs a proof of a disjunction a ∨ b from a proof of the right disjunct b.
List.mem_cons- An element belongs to a cons list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil- The empty list has no elements.
or_false- Disjunction with False simplifies to the proposition itself: (p ∨ False) ↔ p.
- Although the theorem assumes that D is a semicomplete multipartite digraph, the proof only uses this hypothesis to deduce that D has no self-loops (u ≠ v whenever D.Adj u v). The full multipartite structure is not needed.
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.
/-- In a 4-strong semicomplete multipartite digraph, any two pairs of distinct terminals with one pair adjacent in either direction admit vertex-disjoint paths. -/theorem digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked {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 classical have h11 : s₁ ≠ t₁ := by intro heq simp [heq] at hnodup have h21 : s₂ ≠ s₁ := by intro heq subst s₂ simp at hnodup have h2t1 : s₂ ≠ t₁ := by intro heq subst s₂ simp at hnodup have h3s1 : t₂ ≠ s₁ := by intro heq subst t₂ simp at hnodup have h3t1 : t₂ ≠ t₁ := by intro heq subst t₂ simp at hnodup have h22 : s₂ ≠ t₂ := by intro heq subst s₂ simp at hnodup let s : Finset V := {s₁, t₁} have hcard : s.card < 4 := by have hc : s.card = 2 := by dsimp [s] exact Finset.card_pair h11 omega have hs2 : s₂ ∉ s := by simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨h21, h2t1⟩ have ht2 : t₂ ∉ s := by simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨h3s1, h3t1⟩ obtain ⟨p₂, hp₂path, hp₂avoid⟩ := hstrong.2 s hcard s₂ t₂ hs2 ht2 h22 have path_of_adj : ∀ {u v : V}, D.Adj u v → digraph_is_directed_path D [u, v] u v := by intro u v huv have hne : u ≠ v := by rintro rfl exact hmulti.1 u huv unfold digraph_is_directed_path simp [huv, hne] have hs1mem : s₁ ∈ s := by simp [s] have ht1mem : t₁ ∈ s := by simp [s] rcases hadj with hst | hts · refine ⟨[s₁, t₁], p₂, Or.inl (path_of_adj hst), Or.inl hp₂path, ?_⟩ intro a ha hb simp only [List.mem_cons, List.not_mem_nil, or_false] at ha rcases ha with h | h · rw [h] at hb exact (hp₂avoid s₁ hb) hs1mem · rw [h] at hb exact (hp₂avoid t₁ hb) ht1mem · refine ⟨[t₁, s₁], p₂, Or.inr (path_of_adj hts), Or.inl hp₂path, ?_⟩ intro a ha hb simp only [List.mem_cons, List.not_mem_nil, or_false] at ha rcases ha with h | h · rw [h] at hb exact (hp₂avoid t₁ hb) ht1mem · rw [h] at hb exact (hp₂avoid s₁ hb) hs1mem