AFTD Auto-Formalizing Theoretical Domains

tournament_near_regular_of_card_degrees

theoremverifiedoriginal

If a digraph on 2m vertices has exactly m vertices of out-degree m - 1 and exactly m vertices of out-degree m, then it is near-regular.

Statement

theorem tournament_near_regular_of_card_degrees (m : ℕ)
    (T : Digraph (Fin (2 * m))) [DecidableRel T.Adj]
    (hdeg : (Finset.univ.filter (fun v => digraph_out_count T v = m - 1)).card = m ∧
            (Finset.univ.filter (fun v => digraph_out_count T v = m)).card = m) :
    tournament_is_near_regular m T
Related work
arXiv:2610.25886
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

Read back from the Lean

For every natural number $m$ and every directed graph $T$ on vertex set $\mathrm{Fin}(2m)$ with decidable adjacency: if exactly $m$ vertices have out-degree $m - 1$ and exactly $m$ vertices have out-degree $m$, then $T$ is near-regular, meaning that every vertex in $\mathrm{Fin}(2m)$ has out-degree $m - 1$ or $m$.

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

To prove that the digraph is near-regular, we show that every vertex has out-degree m - 1 or m. For m = 0, the vertex set is empty and the claim is vacuous. For m > 0, the set A of vertices of out-degree m - 1 and the set B of vertices of out-degree m are disjoint because m - 1 ≠ m. Since their cardinalities sum to m + m = 2m, which is the total number of vertices in the digraph, their union must comprise all vertices, so every vertex has out-degree m - 1 or m.

  1. Fix an arbitrary vertex v; if m = 0, the claim holds vacuously.

    By definition, a tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m. We introduce an arbitrary vertex v and split on whether m = 0 or m > 0 using Nat.eq_zero_or_pos. When m = 0, the vertex set Fin(0) is empty, and the goal is eliminated vacuously using Fin.elim0.

    lines 7–9

    uses Nat.eq_zero_or_pos, Fin.elim0

      intro v
      rcases Nat.eq_zero_or_pos m with rfl | hm
      · exact Fin.elim0 v
  2. The set A of vertices with out-degree m - 1 and the set B of vertices with out-degree m are disjoint.

    For m > 0, we define A and B as the sets of vertices with out-degree m - 1 and m, respectively. Using disjoint_filter, they are disjoint if no vertex has both out-degrees. Since m > 0 implies m - 1 ≠ m (by arithmetic), assuming an element belongs to both sets gives a contradiction.

    lines 10–17

    uses disjoint_filter

      · open Finset in
        let A := univ.filter (fun v => digraph_out_count T v = m - 1)
        let B := univ.filter (fun v => digraph_out_count T v = m)
        have hdisj : Disjoint A B := by
          rw [disjoint_filter]
          intro x _ h1 h2
          have : m - 1 ≠ m := by omega
          exact this (h1.symm.trans h2)
  3. The union A ∪ B has cardinality 2m.

    Because A and B are disjoint, card_union_of_disjoint implies that |A ∪ B| = |A| + |B|. The hypothesis gives |A| = m and |B| = m, so their union has size m + m = 2m.

    lines 18–20

    uses card_union_of_disjoint

        have hcard : (A ∪ B).card = 2 * m := by
          rw [card_union_of_disjoint hdisj, hdeg.1, hdeg.2]
          omega
  4. The union A ∪ B is the entire vertex set.

    By eq_univ_of_card, any subset of a finite type with the same cardinality as the ambient type is the entire universe. Since Fin(2m) has cardinality 2m by Fintype.card_fin, which matches |A ∪ B|, we obtain A ∪ B = univ.

    lines 21–23

    uses eq_univ_of_card, Fintype.card_fin

        have huniv : A ∪ B = univ := by
          apply eq_univ_of_card
          rw [hcard, Fintype.card_fin]
  5. The vertex v belongs to A ∪ B.

    Every vertex belongs to the universal set univ by mem_univ, so from A ∪ B = univ it follows that v ∈ A ∪ B.

    lines 24–26

    uses mem_univ

        have hv : v ∈ A ∪ B := by
          rw [huniv]
          exact mem_univ v
  6. The out-degree of v is either m - 1 or m.

    Unfolding membership in the union and the filtered sets via mem_union and mem_filter, v ∈ A ∪ B means that v has out-degree m - 1 or out-degree m. Deconstructing this disjunction gives the required conclusion via Or.inl or Or.inr.

    lines 27–30

    uses mem_union, mem_filter, Or.inl, Or.inr

        rw [mem_union, mem_filter, mem_filter] at hv
        rcases hv with ⟨-, h1⟩ | ⟨-, h2⟩
        · exact Or.inl h1
        · exact Or.inr h2
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
Fin.elim0
The empty type Fin(0) has no elements, so any element in it yields a contradiction.
disjoint_filter
Two sub-finsets filtered from the same set are disjoint if and only if no element satisfies both predicates simultaneously.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the type is the entire universe.
Fintype.card_fin
The finite type Fin(n) has cardinality n.
mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
mem_union
An element belongs to the union of two sets if and only if it belongs to the first or the second.
mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Or.inl
Given a proof of proposition a, constructs a proof of the disjunction a ∨ b.
Or.inr
Given a proof of proposition b, constructs a proof of the disjunction a ∨ b.

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

/-- A digraph on 2m vertices with m vertices of out-degree m - 1 and m vertices of out-degree m is near-regular. -/theorem tournament_near_regular_of_card_degrees (m : ℕ)    (T : Digraph (Fin (2 * m))) [DecidableRel T.Adj]    (hdeg : (Finset.univ.filter (fun v => digraph_out_count T v = m - 1)).card = m ∧            (Finset.univ.filter (fun v => digraph_out_count T v = m)).card = m) :    tournament_is_near_regular m T := by  intro v  rcases Nat.eq_zero_or_pos m with rfl | hm  · exact Fin.elim0 v  · open Finset in    let A := univ.filter (fun v => digraph_out_count T v = m - 1)    let B := univ.filter (fun v => digraph_out_count T v = m)    have hdisj : Disjoint A B := by      rw [disjoint_filter]      intro x _ h1 h2      have : m - 1 ≠ m := by omega      exact this (h1.symm.trans h2)    have hcard : (A ∪ B).card = 2 * m := by      rw [card_union_of_disjoint hdisj, hdeg.1, hdeg.2]      omega    have huniv : A ∪ B = univ := by      apply eq_univ_of_card      rw [hcard, Fintype.card_fin]    have hv : v ∈ A ∪ B := by      rw [huniv]      exact mem_univ v    rw [mem_union, mem_filter, mem_filter] at hv    rcases hv with ⟨-, h1⟩ | ⟨-, h2⟩    · exact Or.inl h1    · exact Or.inr h2
See it in the graphDiscuss this resultChallenge it