linkage_of_common_neighbor_right
In 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₁, t₁} and {s₂, t₂}.
Statement
theorem linkage_of_common_neighbor_right {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) (v : V) (hv : v ∉ [s₁, t₁, s₂, t₂]) (hdir : (D.Adj s₂ v ∧ D.Adj v t₂) ∨ (D.Adj t₂ v ∧ D.Adj v 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 digraph_four_strong_semicomplete_multipartite_nonadjacent_pairs_linked
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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₁,…
- 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
This theorem is the symmetric analogue of `linkage_of_common_neighbor`, addressing the case where the intermediate vertex v forms a 2-step directed path with the second terminal pair {s₂, t₂} rather than the first. The proof swaps the order of the terminal pairs to (s₂, t₂, s₁, t₁), checks that distinctness and disjointness from v still hold, applies `linkage_of_common_neighbor`, and finally swaps the resulting paths back to the original order.
The reordered list of terminal vertices [s₂, t₂, s₁, t₁] contains no duplicates.
We expand the duplicate-free condition into pairwise inequalities across the list elements using `simp only` with basic list lemmas (`List.nodup_cons`, `List.mem_cons`, `List.not_mem_nil`, `or_false`, `List.nodup_nil`, `and_true`). Since the original list [s₁, t₁, s₂, t₂] is duplicate-free (`hnodup`), propositional logic and symmetry of equality (`tauto`) verify that the permuted list [s₂, t₂, s₁, t₁] also has distinct entries.
uses
List.nodup_cons,List.mem_cons,List.not_mem_nil,or_false,List.nodup_nil,and_truehave hnodup' : [s₂, t₂, s₁, t₁].Nodup := by simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, or_false, List.nodup_nil, and_true] at hnodup ⊢ tauto
The vertex v does not belong to [s₂, t₂, s₁, t₁].
Rewriting list membership into disjunctions of equalities using `List.mem_cons` and `List.not_mem_nil` allows propositional logic (`tauto`) to deduce v ∉ [s₂, t₂, s₁, t₁] from the hypothesis v ∉ [s₁, t₁, s₂, t₂].
uses
List.mem_cons,List.not_mem_nilhave hv' : v ∉ [s₂, t₂, s₁, t₁] := by simp only [List.mem_cons, List.not_mem_nil] at hv ⊢ tauto
There exist disjoint directed paths p₁ and p₂ such that p₁ unilaterally connects {s₂, t₂} and p₂ unilaterally connects {s₁, t₁}.
We invoke `linkage_of_common_neighbor` with the terminal pairs swapped, using the 4-connectivity of D, the duplicate-free list [s₂, t₂, s₁, t₁], the fact that v avoids these terminals, and the assumption `hdir` that v provides a directed 2-step path between s₂ and t₂. This produces two vertex-disjoint paths: p₁ connecting {s₂, t₂} and p₂ connecting {s₁, t₁}.
uses
linkage_of_common_neighborobtain ⟨p₁, p₂, ⟨h₁, h₂, hd⟩⟩ := linkage_of_common_neighbor D hstrong hnodup' v hv' hdirThe pair (p₂, p₁) witnesses the existence of a unilateral 2-linkage for {s₁, t₁} and {s₂, t₂}.
We provide p₂ as the path between {s₁, t₁} and p₁ as the path between {s₂, t₂}. Their disjointness is immediate from the disjointness of p₁ and p₂ by the symmetry of disjoint lists.
exact ⟨p₂, p₁, h₂, h₁, hd.symm⟩
List.nodup_cons- A non-empty list `a :: l` has no duplicates if and only if `a ∉ l` and `l` has no duplicates.
List.mem_cons- An element belongs to `b :: l` if and only if it equals `b` or belongs to `l`.
List.not_mem_nil- The empty list contains no elements.
or_false- Disjunction of any proposition with `False` simplifies to the proposition itself.
List.nodup_nil- The empty list has no duplicate elements.
and_true- Conjunction of any proposition with `True` simplifies to the proposition itself.
linkage_of_common_neighbor- In a 4-strong digraph, if an external vertex forms a 2-step directed path with the first terminal pair, there exist disjoint unilateral paths connecting the first pair and the second pair.
- On paper, switching the roles of {s₁, t₁} and {s₂, t₂} is treated as immediate by symmetry; in Lean, verifying that the reordered list of terminals remains duplicate-free and avoids v requires explicit verification (lines 12–18).
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 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₁, t₁} and {s₂, t₂}. -/theorem linkage_of_common_neighbor_right {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) (v : V) (hv : v ∉ [s₁, t₁, s₂, t₂]) (hdir : (D.Adj s₂ v ∧ D.Adj v t₂) ∨ (D.Adj t₂ v ∧ D.Adj v 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 simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, or_false, List.nodup_nil, and_true] at hnodup ⊢ tauto have hv' : v ∉ [s₂, t₂, s₁, t₁] := by simp only [List.mem_cons, List.not_mem_nil] at hv ⊢ tauto obtain ⟨p₁, p₂, ⟨h₁, h₂, hd⟩⟩ := linkage_of_common_neighbor D hstrong hnodup' v hv' hdir exact ⟨p₂, p₁, h₂, h₁, hd.symm⟩