regular_tournament_five_nearly_doubly_regular
The case k = 1 of the conjecture, in a stronger form: every regular tournament of order 5 is nearly doubly regular (any two distinct vertices have at most one common out-neighbour), so in particular every maximizer is.
Statement
theorem regular_tournament_five_nearly_doubly_regular (D : Digraph (Fin 5))
[DecidableRel D.Adj] (hD : digraph_is_tournament D)
(hreg : ∀ v, digraph_out_count D v = 2) :
∀ i j, i ≠ j → digraph_common_out_count D i j = 0 ∨ digraph_common_out_count D i j = 1- Formalizes
- arXiv:2610.25886 (Extremal arborescences in graph orientations), Conjecture 6.1; the order 5 case, checked by computation in the paper
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- digraph_common_out_countc_ij: the number of common out-neighbours of the vertices i and j of a digraph on Fin n.
The proof, explained
The proof proceeds by ruling out the possibility that two vertices share two common out-neighbours. For any two distinct vertices i and j in a 2-regular tournament, their common out-neighbourhood is contained in the out-neighbourhood of i, which has size 2, so the number of common out-neighbours can only be 0, 1, or 2. If it were 2, cardinality considerations would force the out-neighbourhoods of i and j to be identical. But between any two distinct vertices in a tournament there is an edge in one direction, and either direction would force a self-loop (either j → j or i → i), contradicting irreflexivity.
For any distinct vertices i and j, their common out-neighbourhood is a subset of both N⁺(i) and N⁺(j).
Fix distinct vertices i and j. By unfolding the definition of the filtered sets using Finset.mem_filter, any vertex w that has directed edges from both i and j is in particular an out-neighbour of i and an out-neighbour of j.
uses
Finset.mem_filterintro i j hij have hsub_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆ (Finset.filter (fun w => D.Adj i w) Finset.univ) := by intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.1⟩ have hsub_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆ (Finset.filter (fun w => D.Adj j w) Finset.univ) := by intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.2⟩
The number of common out-neighbours of i and j is 0, 1, or 2.
Because the common out-neighbourhood is contained in N⁺(i), which has size 2 by 2-regularity, its cardinality is at most 2 (Finset.card_le_card). Linear arithmetic over ℕ (omega) then deduces that this count must be 0, 1, or 2.
uses
Finset.card_le_cardhave hle : digraph_common_out_count D i j ≤ 2 := by have h1 := Finset.card_le_card hsub_i have h2 := hreg i exact h1.trans_eq h2 have hcases : digraph_common_out_count D i j = 0 ∨ digraph_common_out_count D i j = 1 ∨ digraph_common_out_count D i j = 2 := by omega
The cases where the common out-neighbour count is 0 or 1 immediately satisfy the goal.
A case split on the three possible values leaves only the count 2 to consider, as 0 and 1 satisfy the required disjunction directly.
rcases hcases with h0 | h1 | h2 · left; exact h0 · right; exact h1
If the common out-neighbour count were 2, then N⁺(i) and N⁺(j) would be identical.
Assume for contradiction that the count is 2. Both out-neighbourhoods N⁺(i) and N⁺(j) also have size 2 by regularity. A subset of the same cardinality as the ambient finite set must be the entire set (Finset.eq_of_subset_of_card_le), so both N⁺(i) and N⁺(j) equal their common intersection, hence N⁺(i) = N⁺(j).
uses
Finset.eq_of_subset_of_card_le· exfalso have hcard_comm : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ).card = 2 := h2 have hcard_i : (Finset.filter (fun w => D.Adj i w) Finset.univ).card = 2 := hreg i have hcard_j : (Finset.filter (fun w => D.Adj j w) Finset.univ).card = 2 := hreg j have heq_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) = (Finset.filter (fun w => D.Adj i w) Finset.univ) := by apply Finset.eq_of_subset_of_card_le hsub_i rw [hcard_comm, hcard_i] have heq_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) = (Finset.filter (fun w => D.Adj j w) Finset.univ) := by apply Finset.eq_of_subset_of_card_le hsub_j rw [hcard_comm, hcard_j] have hij_eq : (Finset.filter (fun w => D.Adj i w) Finset.univ) = (Finset.filter (fun w => D.Adj j w) Finset.univ) := by rw [← heq_i, ← heq_j]
If there is an edge from i to j, we obtain a contradiction.
Since i ≠ j, tournament completeness ensures exactly one edge between i and j. If i → j, then j ∈ N⁺(i). Since N⁺(i) = N⁺(j), this gives j ∈ N⁺(j), meaning j → j, which contradicts the irreflexivity of the tournament (hD.1).
uses
Finset.mem_filter,Finset.mem_univhave htourn := hD.2 i j hij by_cases hadj : D.Adj i j · have hj_in_i : j ∈ Finset.filter (fun w => D.Adj i w) Finset.univ := by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ j, hadj⟩ rw [hij_eq] at hj_in_i rw [Finset.mem_filter] at hj_in_i exact hD.1 j hj_in_i.2
If instead there is an edge from j to i, we also obtain a contradiction.
If there is no edge from i to j, the tournament condition forces an edge j → i. Then i ∈ N⁺(j), which via N⁺(i) = N⁺(j) implies i ∈ N⁺(i) and therefore i → i. This again contradicts irreflexivity, ruling out a common out-neighbour count of 2 and completing the proof.
uses
Finset.mem_filter,Finset.mem_univ· have h_ji : D.Adj j i := by by_contra h_not_ji apply hadj rwa [htourn] have hi_in_j : i ∈ Finset.filter (fun w => D.Adj j w) Finset.univ := by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ i, h_ji⟩ rw [← hij_eq] at hi_in_j rw [Finset.mem_filter] at hi_in_j exact hD.1 i hi_in_j.2
Finset.mem_filter- An element a belongs to the filtered sub-collection of s satisfying predicate p if and only if a ∈ s and p(a) holds.
Finset.card_le_card- If a finite set s is a subset of a finite set t, then the cardinality of s is at most that of t.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s| for finite sets s and t, then s = t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
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.
theorem regular_tournament_five_nearly_doubly_regular (D : Digraph (Fin 5)) [DecidableRel D.Adj] (hD : digraph_is_tournament D) (hreg : ∀ v, digraph_out_count D v = 2) : ∀ i j, i ≠ j → digraph_common_out_count D i j = 0 ∨ digraph_common_out_count D i j = 1 := by intro i j hij have hsub_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆ (Finset.filter (fun w => D.Adj i w) Finset.univ) := by intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.1⟩ have hsub_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) ⊆ (Finset.filter (fun w => D.Adj j w) Finset.univ) := by intro w hw; rw [Finset.mem_filter] at hw ⊢; exact ⟨hw.1, hw.2.2⟩ have hle : digraph_common_out_count D i j ≤ 2 := by have h1 := Finset.card_le_card hsub_i have h2 := hreg i exact h1.trans_eq h2 have hcases : digraph_common_out_count D i j = 0 ∨ digraph_common_out_count D i j = 1 ∨ digraph_common_out_count D i j = 2 := by omega rcases hcases with h0 | h1 | h2 · left; exact h0 · right; exact h1 · exfalso have hcard_comm : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ).card = 2 := h2 have hcard_i : (Finset.filter (fun w => D.Adj i w) Finset.univ).card = 2 := hreg i have hcard_j : (Finset.filter (fun w => D.Adj j w) Finset.univ).card = 2 := hreg j have heq_i : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) = (Finset.filter (fun w => D.Adj i w) Finset.univ) := by apply Finset.eq_of_subset_of_card_le hsub_i rw [hcard_comm, hcard_i] have heq_j : (Finset.filter (fun v => D.Adj i v ∧ D.Adj j v) Finset.univ) = (Finset.filter (fun w => D.Adj j w) Finset.univ) := by apply Finset.eq_of_subset_of_card_le hsub_j rw [hcard_comm, hcard_j] have hij_eq : (Finset.filter (fun w => D.Adj i w) Finset.univ) = (Finset.filter (fun w => D.Adj j w) Finset.univ) := by rw [← heq_i, ← heq_j] have htourn := hD.2 i j hij by_cases hadj : D.Adj i j · have hj_in_i : j ∈ Finset.filter (fun w => D.Adj i w) Finset.univ := by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ j, hadj⟩ rw [hij_eq] at hj_in_i rw [Finset.mem_filter] at hj_in_i exact hD.1 j hj_in_i.2 · have h_ji : D.Adj j i := by by_contra h_not_ji apply hadj rwa [htourn] have hi_in_j : i ∈ Finset.filter (fun w => D.Adj j w) Finset.univ := by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ i, h_ji⟩ rw [← hij_eq] at hi_in_j rw [Finset.mem_filter] at hi_in_j exact hD.1 i hi_in_j.2