digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_right
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
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linkedLet 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…
- 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_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…
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.
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.
uses
List.nodup_cons,List.mem_cons,List.not_mem_nil,or_false,not_or,List.nodup_nil,and_truehave 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
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.
uses
digraph_four_strong_semicomplete_multipartite_adjacent_pair_linkedobtain ⟨q₁, q₂, hq₁, hq₂, hdisj⟩ := digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked D hstrong hmulti hnodup' hadjThere 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.
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
- The distinctness hypothesis is formalized using ordered lists (`List.Nodup [s₁, t₁, s₂, t₂]`), requiring an explicit lemma step (lines 12–18) to reorder the list to `[s₂, t₂, s₁, t₁]`, which is mathematically trivial.
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, 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⟩