linkage_of_common_neighbor
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 {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 op_620_four_strong_semicomplete_multipartite_unilaterally_two_linked
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- short_path_gives_linkage_four_strongIn 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…
- 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…
- 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…
- Used by 1
- linkage_of_common_neighbor_rightIn 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
The proof proceeds by case analysis on the direction of the 2-step path through the outside vertex $v$, either $s₁ \to v \to t₁$ or $t₁ \to v \to s₁$. In either case, the 3-vertex sequence forms a directed path between $s₁$ and $t₁$ of length 3 (consisting of 2 edges). Because $v \notin \{s₁, t₁, s₂, t₂\}$ and the terminal vertices are pairwise distinct, this short path avoids both $s₂$ and $t₂$. The theorem `short_path_gives_linkage_four_strong` then directly guarantees the existence of a unilateral 2-linkage in the 4-strong digraph.
The distinctness assumption on $\{s₁, t₁, s₂, t₂\}$ and the condition $v \notin [s₁, t₁, s₂, t₂]$ are simplified into explicit pairwise disequalities.
We make a copy of `hnodup` as `h_nodup_simped` and rewrite both `h_nodup_simped` and `hv` using `List.nodup_cons`, `List.mem_cons`, `List.not_mem_nil`, and `not_false_eq_true`. This unpacks the list-level assertions into propositional conjunctions of inequalities, making pairwise disequalities between $v$ and the terminal vertices $\{s₁, t₁, s₂, t₂\}$ readily available.
uses
List.nodup_cons,List.mem_cons,List.not_mem_nil,not_false_eq_truehave h_nodup_simped := hnodup simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] at h_nodup_simped hv
In the forward case ($s₁ \to v$ and $v \to t₁$), the 3-vertex sequence $[s₁, v, t₁]$ is a directed path in $D$ from $s₁$ to $t₁$.
We case split on `hdir`. In the first case, we have directed edges $s₁ \to v$ and $v \to t₁$. We construct `hpath` showing $[s₁, v, t₁]$ is a directed path: the chain condition holds by simplification with the two edge hypotheses; the absence of duplicates in $[s₁, v, t₁]$ reduces by `simp only` and is closed by propositional logic (`tauto`) from the pairwise disequalities; and the endpoints match $s₁$ and $t₁$ by reflexivity (`rfl`).
uses
List.nodup_cons,List.mem_cons,List.not_mem_nil,not_false_eq_truecases hdir with | inl h => have hpath : digraph_is_directed_path D [s₁, v, t₁] s₁ t₁ := by refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩ simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] tauto
In the forward case ($s₁ \to v \to t₁$), the unilateral 2-linkage exists.
We apply the lemma `short_path_gives_linkage_four_strong` with the path $[s₁, v, t₁]$. The path connects $s₁$ to $t₁$ via `Or.inl hpath`, has length 3 which satisfies the length requirement $3 \le 3$ by reflexivity (`le_rfl`), and avoids $s₂$ and $t₂$. Expanding the avoidance condition via `List.mem_cons` and `List.not_mem_nil`, propositional logic (`tauto`) verifies that neither $s₂$ nor $t₂$ coincides with any vertex in $[s₁, v, t₁]$, concluding this case.
uses
short_path_gives_linkage_four_strong,Or.inl,le_rfl,List.mem_cons,List.not_mem_nilapply short_path_gives_linkage_four_strong D hstrong hnodup [s₁, v, t₁] (Or.inl hpath) le_rfl simp only [List.mem_cons, List.not_mem_nil] tauto
In the reverse case ($t₁ \to v$ and $v \to s₁$), the 3-vertex sequence $[t₁, v, s₁]$ is a directed path in $D$ from $t₁$ to $s₁$.
In the second branch of `hdir`, we have directed edges $t₁ \to v$ and $v \to s₁$. Symmetrically to the first case, we construct `hpath` showing $[t₁, v, s₁]$ is a directed path from $t₁$ to $s₁$: the chain condition holds by the edge hypotheses, the endpoints are $t₁$ and $s₁$ by reflexivity, and the list has no duplicates by propositional logic (`tauto`) after expanding via `simp only`.
uses
List.nodup_cons,List.mem_cons,List.not_mem_nil,not_false_eq_true| inr h => have hpath : digraph_is_directed_path D [t₁, v, s₁] t₁ s₁ := by refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩ simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] tautoIn the reverse case ($t₁ \to v \to s₁$), the unilateral 2-linkage exists, concluding the proof.
We apply `short_path_gives_linkage_four_strong` with $[t₁, v, s₁]$ via `Or.inr hpath` and length bound $3 \le 3$ by `le_rfl`. After expanding list membership with `List.mem_cons` and `List.not_mem_nil`, propositional logic (`tauto`) confirms that $s₂$ and $t₂$ are distinct from $t₁, v, s₁$, completing the proof.
uses
short_path_gives_linkage_four_strong,Or.inr,le_rfl,List.mem_cons,List.not_mem_nilapply short_path_gives_linkage_four_strong D hstrong hnodup [t₁, v, s₁] (Or.inr hpath) le_rfl simp only [List.mem_cons, List.not_mem_nil] tauto
List.nodup_cons- A list $a :: l$ has no duplicate elements if and only if $a \notin l$ and $l$ has no duplicate elements.
List.mem_cons- An element $x$ belongs to $b :: l$ if and only if $x = b$ or $x \in l$.
List.not_mem_nil- No element belongs to the empty list.
not_false_eq_true- The negation of `False` is equal to `True`.
short_path_gives_linkage_four_strong- In a 4-strong digraph, if $\{s₁, t₁, s₂, t₂\}$ are pairwise distinct and there is a directed path between $s₁$ and $t₁$ (in either direction) of length at most 3 avoiding $s₂$ and $t₂$, then a unilateral 2-linkage exists for $\{s₁, t₁\}$ and $\{s₂, t₂\}$.
Or.inl- From a proof of $A$, infer the disjunction $A \vee B$.
Or.inr- From a proof of $B$, infer the disjunction $A \vee B$.
le_rfl- The preorder relation $\le$ is reflexive ($a \le a$).
- The verification of pairwise disequalities among vertices in $\{s₁, t₁, s₂, t₂, v\}$ is handled by `tauto` after expanding list distinctness and membership via `simp only`.
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 an outside vertex forms a 2-step directed path between {s₁, t₁}, then unilateral 2-linkage exists in a 4-strong digraph. -/theorem linkage_of_common_neighbor {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 h_nodup_simped := hnodup simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] at h_nodup_simped hv cases hdir with | inl h => have hpath : digraph_is_directed_path D [s₁, v, t₁] s₁ t₁ := by refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩ simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] tauto apply short_path_gives_linkage_four_strong D hstrong hnodup [s₁, v, t₁] (Or.inl hpath) le_rfl simp only [List.mem_cons, List.not_mem_nil] tauto | inr h => have hpath : digraph_is_directed_path D [t₁, v, s₁] t₁ s₁ := by refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩ simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] tauto apply short_path_gives_linkage_four_strong D hstrong hnodup [t₁, v, s₁] (Or.inr hpath) le_rfl simp only [List.mem_cons, List.not_mem_nil] tauto