AFTD Auto-Formalizing Theoretical Domains

exists_near_regular_tournament_four

theoremverified

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.

  1. 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.

    line 22

    uses exists_near_regular_tournament_four_T, exists_near_regular_tournament_four_dec

      refine ⟨exists_near_regular_tournament_four_T, exists_near_regular_tournament_four_dec, ?_, ?_⟩
  2. `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`).

    lines 23–24

    uses digraph_is_tournament, exists_near_regular_tournament_four_T

      · dsimp [digraph_is_tournament, exists_near_regular_tournament_four_T]
        decide
  3. `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.

    lines 25–26

    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.

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

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