exists_near_regular_tournament_four
There exists a near-regular tournament on 4 vertices.
Statement
theorem exists_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 2
- 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.
Read back from the Lean
There exists a directed graph $T$ on the vertex type Fin 4 and a decidability instance for its adjacency relation such that:
1. $T$ is a tournament (it has no self-loops, and for every pair of distinct vertices $x \neq y$, exactly one of $x \to y$ or $y \to x$ is an edge), and
2. $T$ is near-regular with parameter $m = 2$, meaning that for every vertex $v : \text{Fin 4}$, the out-degree of $v$ is either $1$ ($2 - 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
The proof constructs an explicit directed graph on 4 vertices with edges (0, 1), (0, 2), (3, 0), (1, 2), (1, 3), and (2, 3). It has no self-loops and contains exactly one directed edge between each distinct pair of vertices, making it a tournament. The out-degrees of the vertices are 2, 2, 1, and 1, so every vertex has out-degree in {1, 2}, satisfying near-regularity for m = 2. Both tournamenthood and near-regularity are verified by exhaustive computation on the finite domain.
It suffices to show that the explicit directed graph `exists_near_regular_tournament_four_T` is a tournament and is near-regular with parameter 2.
We provide `exists_near_regular_tournament_four_T` as a candidate witness on 4 vertices, along with `exists_near_regular_tournament_four_dec` establishing that its adjacency relation is decidable. This instantiates the existential quantifier, leaving two subgoals: verifying that the graph is a tournament, and verifying that it is near-regular.
uses
exists_near_regular_tournament_four_T,exists_near_regular_tournament_four_decrefine ⟨exists_near_regular_tournament_four_T, exists_near_regular_tournament_four_dec, ?_, ?_⟩`exists_near_regular_tournament_four_T` is a tournament.
We expand the definition of a tournament into two conditions: no vertex has a self-loop, and between any two distinct vertices, exactly one directed edge exists. Since the vertex set `Fin 4` is finite, Lean checks all 4 vertices and all 16 pairs by exhaustive boolean evaluation (`decide`).
uses
digraph_is_tournament,exists_near_regular_tournament_four_T· dsimp [digraph_is_tournament, exists_near_regular_tournament_four_T] decide
`exists_near_regular_tournament_four_T` is near-regular with parameter 2.
We unfold the definitions of near-regularity and out-degree, which require every vertex to have out-degree $2 - 1 = 1$ or $2$. Lean computes the out-degree of each of the 4 vertices—yielding 2 for vertices 0 and 1, and 1 for vertices 2 and 3—and verifies by decision procedure (`decide`) that every vertex satisfies the condition.
uses
tournament_is_near_regular,digraph_out_count,exists_near_regular_tournament_four_T· dsimp [tournament_is_near_regular, digraph_out_count, exists_near_regular_tournament_four_T] decide
exists_near_regular_tournament_four_T- The concrete directed graph on four vertices {0, 1, 2, 3} with directed edges (0, 1), (0, 2), (3, 0), (1, 2), (1, 3), and (2, 3).
exists_near_regular_tournament_four_dec- The decidability instance for the adjacency relation of `exists_near_regular_tournament_four_T`.
digraph_is_tournament- The property that a directed graph has no self-loops and, for every pair of distinct vertices, contains a directed edge in exactly one direction.
tournament_is_near_regular- The property that in a tournament on 2m vertices, every vertex has out-degree equal to m - 1 or m.
digraph_out_count- The out-degree of a vertex in a finite directed graph, defined as the number of outgoing edges from that vertex.
- The verification that the candidate graph satisfies the tournament axioms and the near-regularity condition is carried out entirely by computational evaluation (`decide`) over the finite domain `Fin 4`.
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.
def exists_near_regular_tournament_four_adj_bool (i j : Fin 4) : Bool := match i, j with | 0, 1 => true | 0, 2 => true | 3, 0 => true | 1, 2 => true | 1, 3 => true | 2, 3 => true | _, _ => falsedef exists_near_regular_tournament_four_T : Digraph (Fin 4) := ⟨fun i j => exists_near_regular_tournament_four_adj_bool i j = true⟩instance exists_near_regular_tournament_four_dec : DecidableRel exists_near_regular_tournament_four_T.Adj := fun i j => inferInstanceAs (Decidable (exists_near_regular_tournament_four_adj_bool i j = true))/-- Witness that near-regular tournaments of order 4 exist. -/theorem exists_near_regular_tournament_four : ∃ (T : Digraph (Fin 4)) (_ : DecidableRel T.Adj), digraph_is_tournament T ∧ tournament_is_near_regular 2 T := by refine ⟨exists_near_regular_tournament_four_T, exists_near_regular_tournament_four_dec, ?_, ?_⟩ · dsimp [digraph_is_tournament, exists_near_regular_tournament_four_T] decide · dsimp [tournament_is_near_regular, digraph_out_count, exists_near_regular_tournament_four_T] decide