exists_not_near_regular_tournament_four
There exists a tournament on 4 vertices that is not near-regular.
Statement
theorem exists_not_near_regular_tournament_four :
∃ (T : Digraph (Fin 4)) (_ : DecidableRel T.Adj),
digraph_is_tournament T ∧ ¬ tournament_is_near_regular 2 T- Source
- folklore
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- tournament_is_near_regularA tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m.
- 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.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
Read back from the Lean
There exists a directed graph $T$ on the vertex set $\text{Fin } 4$ and a decidability witness for the adjacency relation $T.\text{Adj}$ such that: 1. $T$ is a tournament (for all $x \in \text{Fin } 4$, $T$ does not have a self-loop at $x$, and for all $x, y \in \text{Fin } 4$ with $x \ne y$, $T.\text{Adj } x\ y \iff \neg T.\text{Adj } y\ x$), and 2. $T$ is not near-regular with parameter $m = 2$ (it is not the case that every vertex $v \in \text{Fin } 4$ has out-degree equal to $2 - 1 = 1$ or $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
We exhibit the transitive tournament on four vertices {0, 1, 2, 3}, where a directed edge points from i to j if and only if i < j. This graph is irreflexive and complete, and therefore a tournament. In any near-regular tournament of order 4 (parameter m = 2), every vertex must have out-degree 1 or 2, but vertex 0 has out-degree 3 since it beats all other vertices, yielding a contradiction.
Let D be the directed graph on Fin 4 where an edge exists from i to j if and only if i < j; it suffices to show that its adjacency relation is decidable, that D is a tournament, and that D is not near-regular.
We choose the transitive tournament on the four vertices {0, 1, 2, 3}, ordered by the standard strict inequality i < j, as the witness for the existential statement. Providing D splits the existential goal into three subgoals: decidability of adjacency, the tournament conditions, and the negation of near-regularity.
let D : Digraph (Fin 4) := ⟨fun i j => i < j⟩ refine ⟨D, ?_, ?_, ?_⟩
The adjacency relation of D is decidable.
Typeclass synthesis automatically infers that the adjacency relation (strict inequality < on Fin 4) is decidable.
· infer_instanceD is a tournament.
Unfolding the definition of a tournament, we must show that D has no self-loops and that for any two distinct vertices, exactly one directed edge exists between them. Irreflexivity holds because < is strictly irreflexive by lt_irrefl. For distinct vertices x ≠ y, trichotomy of the total order ensures that x < y if and only if ¬(y < x), which linear arithmetic (omega) verifies in both directions.
uses
lt_irrefl· dsimp [D, digraph_is_tournament] constructor · intro x; exact lt_irrefl x · intro x y hxy constructor <;> intro h <;> omega
D is not near-regular.
Suppose, for contradiction, that D were near-regular with parameter m = 2. By definition, every vertex in a near-regular tournament of order 4 must have out-degree equal to 2 - 1 = 1 or 2. Specializing to vertex 0, its out-degree must be 1 or 2. However, vertex 0 beats vertices 1, 2, and 3, giving it an out-degree of 3, as verified by finite evaluation (decide). Substituting 3 into the condition yields 3 = 1 ∨ 3 = 2, which integer arithmetic (omega) refutes.
· intro h have h0 := h 0 have hc : digraph_out_count D 0 = 3 := by decide rw [hc] at h0 omega
lt_irrefl- Strict inequality in a preorder is irreflexive: no element is strictly less than itself (¬ a < a).
- The out-degree calculation `digraph_out_count D 0 = 3` at line 15 is verified by Lean's computational kernel (`decide`), which filters the finite universe `Fin 4` and counts the elements.
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.
/-- Witness that not all tournaments of order 4 are near-regular. -/theorem exists_not_near_regular_tournament_four : ∃ (T : Digraph (Fin 4)) (_ : DecidableRel T.Adj), digraph_is_tournament T ∧ ¬ tournament_is_near_regular 2 T := by let D : Digraph (Fin 4) := ⟨fun i j => i < j⟩ refine ⟨D, ?_, ?_, ?_⟩ · infer_instance · dsimp [D, digraph_is_tournament] constructor · intro x; exact lt_irrefl x · intro x y hxy constructor <;> intro h <;> omega · intro h have h0 := h 0 have hc : digraph_out_count D 0 = 3 := by decide rw [hc] at h0 omega