AFTD Auto-Formalizing Theoretical Domains

digraph_four_strong_tournament_unilaterally_two_linked

theoremverifiedoriginal

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.

  1. The tournament is unilaterally 2-linked.

    Every tournament has edges between distinct vertices.

    lines 45–68

      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⟩

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

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⟩
See it in the graphDiscuss this resultChallenge it