digraph_four_strong_tournament_unilaterally_two_linked
Let D be a digraph on a finite type V. If D is a tournament and D is 4-strong, then D is unilaterally 2-linked.
Statement
theorem digraph_four_strong_tournament_unilaterally_two_linked {V : Type*} [Fintype V] (D : Digraph V) (htourn : digraph_is_tournament D) (hstrong : digraph_is_k_strong D 4) : digraph_is_unilaterally_two_linked D
- Related work
- arXiv:2610.36895 Sec. 1 and Sec. 5
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- 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_unilaterally_two_linkedA digraph D is unilaterally 2-linked if for every four pairwise distinct vertices s₁, t₁, s₂, t₂ in D, there exist vertex-disjoint…
- 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…
Read back from the Lean
For every finite type $V$ and every directed graph $D$ on $V$: If: 1. $D$ is a tournament, meaning that no vertex has a self-loop (for all $x \in V$, $\neg D.\mathrm{Adj}(x, x)$), and for all distinct vertices $x, y \in V$, exactly one of $(x, y)$ or $(y, x)$ is an edge in $D$ ($D.\mathrm{Adj}(x, y) \iff \neg D.\mathrm{Adj}(y, x)$); and 2. $D$ is 4-strongly connected, meaning that $|V| > 4$, and for every subset $s \subseteq V$ with $|s| < 4$ and all distinct vertices $u, v \in V \setminus s$, there exists a directed path in $D$ from $u$ to $v$ avoiding $s$ (all vertices of the path lie in $V \setminus s$); Then $D$ is unilaterally 2-linked, meaning that for any four pairwise distinct vertices $s_1, t_1, s_2, t_2 \in V$, there exist vertex-disjoint directed paths $p_1$ and $p_2$ in $D$ such that: - $p_1$ is either a directed path from $s_1$ to $t_1$ or from $t_1$ to $s_1$, and - $p_2$ is either a directed path from $s_2$ to $t_2$ or from $t_2$ to $s_2$.
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
In any tournament, distinct vertices are connected by an edge in at least one direction. For any four distinct vertices, the two-element lists formed by the pairs provide mutually disjoint paths of length 1, making the tournament unilaterally 2-linked without even using the 4-strong hypothesis.
The tournament is unilaterally 2-linked.
Every tournament has edges between distinct vertices.
obtain ⟨hirr, hanti⟩ := htourn intro s₁ t₁ s₂ t₂ hnd obtain ⟨hd11, hd12, hd21, hd22⟩ := digraph_four_strong_tournament_unilaterally_two_linked_lists_disjoint hnd simp at hnd have hne1 : s₁ ≠ t₁ := hnd.1.1 have hne2 : s₂ ≠ t₂ := hnd.2.2 have h1 : D.Adj s₁ t₁ ∨ D.Adj t₁ s₁ := by by_cases hh : D.Adj s₁ t₁ · exact Or.inl hh · exact Or.inr (by_contra fun hc => hh ((hanti s₁ t₁ hne1).mpr hc)) have h2 : D.Adj s₂ t₂ ∨ D.Adj t₂ s₂ := by by_cases hh : D.Adj s₂ t₂ · exact Or.inl hh · exact Or.inr (by_contra fun hc => hh ((hanti s₂ t₂ hne2).mpr hc)) rcases h1 with h1 | h1 <;> rcases h2 with h2 | h2 · exact ⟨[s₁,t₁], [s₂,t₂], Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd11⟩ · exact ⟨[s₁,t₁], [t₂,s₂], Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd12⟩ · exact ⟨[t₁,s₁], [s₂,t₂], Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd21⟩ · exact ⟨[t₁,s₁], [t₂,s₂], Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd22⟩
- Unresolved check: no step explains line(s) 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 -- every tactic of the proof has to belong to some step
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.
private lemma digraph_four_strong_tournament_unilaterally_two_linked_lists_disjoint {V : Type*} {a b c d : V} (h : [a,b,c,d].Nodup) : List.Disjoint [a,b] [c,d] ∧ List.Disjoint [a,b] [d,c] ∧ List.Disjoint [b,a] [c,d] ∧ List.Disjoint [b,a] [d,c] := by simp at h obtain ⟨⟨hab, hac, had⟩, ⟨hbc, hbd⟩, hcd⟩ := h refine ⟨?_, ?_, ?_, ?_⟩ · simp only [List.Disjoint, List.mem_cons, List.not_mem_nil, or_false] rintro x (hxa | hxb) (hyc | hyd) · exact hac (hxa.symm.trans hyc) · exact had (hxa.symm.trans hyd) · exact hbc (hxb.symm.trans hyc) · exact hbd (hxb.symm.trans hyd) · simp only [List.Disjoint, List.mem_cons, List.not_mem_nil, or_false] rintro x (hxa | hxb) (hyd | hyc) · exact had (hxa.symm.trans hyd) · exact hac (hxa.symm.trans hyc) · exact hbd (hxb.symm.trans hyd) · exact hbc (hxb.symm.trans hyc) · simp only [List.Disjoint, List.mem_cons, List.not_mem_nil, or_false] rintro x (hxb | hxa) (hyc | hyd) · exact hbc (hxb.symm.trans hyc) · exact hbd (hxb.symm.trans hyd) · exact hac (hxa.symm.trans hyc) · exact had (hxa.symm.trans hyd) · simp only [List.Disjoint, List.mem_cons, List.not_mem_nil, or_false] rintro x (hxb | hxa) (hyd | hyc) · exact hbd (hxb.symm.trans hyd) · exact hbc (hxb.symm.trans hyc) · exact had (hxa.symm.trans hyd) · exact hac (hxa.symm.trans hyc)private lemma digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj {V : Type*} (D : Digraph V) (hirr : ∀ x, ¬ D.Adj x x) {x y : V} (hxy : D.Adj x y) : digraph_is_directed_path D [x, y] x y := by have hne : x ≠ y := by rintro rfl; exact hirr x hxy exact ⟨by simp [hxy], by simp [hne], rfl, rfl⟩/-- Every 4-strong tournament is unilaterally 2-linked. -/theorem digraph_four_strong_tournament_unilaterally_two_linked {V : Type*} [Fintype V] (D : Digraph V) (htourn : digraph_is_tournament D) (hstrong : digraph_is_k_strong D 4) : digraph_is_unilaterally_two_linked D := by obtain ⟨hirr, hanti⟩ := htourn intro s₁ t₁ s₂ t₂ hnd obtain ⟨hd11, hd12, hd21, hd22⟩ := digraph_four_strong_tournament_unilaterally_two_linked_lists_disjoint hnd simp at hnd have hne1 : s₁ ≠ t₁ := hnd.1.1 have hne2 : s₂ ≠ t₂ := hnd.2.2 have h1 : D.Adj s₁ t₁ ∨ D.Adj t₁ s₁ := by by_cases hh : D.Adj s₁ t₁ · exact Or.inl hh · exact Or.inr (by_contra fun hc => hh ((hanti s₁ t₁ hne1).mpr hc)) have h2 : D.Adj s₂ t₂ ∨ D.Adj t₂ s₂ := by by_cases hh : D.Adj s₂ t₂ · exact Or.inl hh · exact Or.inr (by_contra fun hc => hh ((hanti s₂ t₂ hne2).mpr hc)) rcases h1 with h1 | h1 <;> rcases h2 with h2 | h2 · exact ⟨[s₁,t₁], [s₂,t₂], Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd11⟩ · exact ⟨[s₁,t₁], [t₂,s₂], Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd12⟩ · exact ⟨[t₁,s₁], [s₂,t₂], Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inl (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd21⟩ · exact ⟨[t₁,s₁], [t₂,s₂], Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h1), Or.inr (digraph_four_strong_tournament_unilaterally_two_linked_path_of_adj D hirr h2), hd22⟩