AFTD Auto-Formalizing Theoretical Domains

exists_not_near_regular_tournament_four

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

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

    lines 5–6

      let D : Digraph (Fin 4) := ⟨fun i j => i < j⟩
      refine ⟨D, ?_, ?_, ?_⟩
  2. The adjacency relation of D is decidable.

    Typeclass synthesis automatically infers that the adjacency relation (strict inequality < on Fin 4) is decidable.

    line 7

      · infer_instance
  3. D 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.

    lines 8–12

    uses lt_irrefl

      · dsimp [D, digraph_is_tournament]
        constructor
        · intro x; exact lt_irrefl x
        · intro x y hxy
          constructor <;> intro h <;> omega
  4. 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.

    lines 13–17

      · 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).

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

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