AFTD Auto-Formalizing Theoretical Domains

tournament_near_regular_card_degrees

theoremverifiedoriginal

In any near-regular tournament on 2m vertices with m ≥ 1, exactly m vertices have out-degree m - 1 and exactly m vertices have out-degree m.

Statement

theorem tournament_near_regular_card_degrees (m : ℕ) (hm : 1 ≤ m)
    (T : Digraph (Fin (2 * m))) [DecidableRel T.Adj] (hT : digraph_is_tournament T)
    (hnr : tournament_is_near_regular m T) :
    (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
Related work
arXiv:2610.25886
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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.
  • tournament_sum_out_countIn a tournament T on Fin n, the out-degrees sum to the number of unordered pairs: ∑_i d_i = n(n-1)/2.
  • 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

For any natural number $m$ with $1 \le m$, and any directed graph $T$ on the vertex set $\mathrm{Fin}(2m)$ with decidable adjacency relation $T.\mathrm{Adj}$, assuming: 1. $T$ is a tournament (i.e., no vertex has a self-loop, and for every pair of distinct vertices $x \ne y$, exactly one of $T.\mathrm{Adj}(x, y)$ or $T.\mathrm{Adj}(y, x)$ holds), and 2. $T$ is near-regular (i.e., for every vertex $v \in \mathrm{Fin}(2m)$, the out-degree of $v$ in $T$ is either $m - 1$ or $m$), then the number of vertices in $\mathrm{Fin}(2m)$ with out-degree $m - 1$ is $m$, and the number of vertices in $\mathrm{Fin}(2m)$ with out-degree $m$ is $m$ (where the out-degree of $v$ is the cardinality of $\{w \in \mathrm{Fin}(2m) \mid T.\mathrm{Adj}(v, w)\}$).

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 partitions the 2m vertices of the near-regular tournament into two disjoint sets: A (vertices with out-degree m - 1) and B (vertices with out-degree m). This gives the first equation on their sizes: |A| + |B| = 2m. Since the sum of all out-degrees in any tournament on 2m vertices is 2m(2m - 1)/2 = m(2m - 1), summing out-degrees over A and B yields the second equation |A|(m - 1) + |B|m = m(2m - 1). Solving this 2 × 2 linear system uniquely determines that |A| = m and |B| = m.

  1. Let A be the set of vertices with out-degree m - 1 and B be the set of vertices with out-degree m.

    We partition the vertices conceptually into the subset A of vertices having out-degree m - 1 and the subset B of vertices having out-degree m.

    lines 7–9

      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)
  2. The sets A and B are disjoint.

    By `disjoint_filter`, it suffices to show that no vertex has out-degree both m - 1 and m. Since m ≥ 1, m - 1 ≠ m, so no vertex can belong to both sets.

    lines 10–14

    uses disjoint_filter

      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 is the universal set of all vertices.

    By set extensionality, a vertex belongs to A ∪ B if and only if its out-degree is m - 1 or m. This holds for every vertex by the definition of near-regularity (`hnr`).

    lines 15–20

    uses mem_univ, iff_true, mem_union, mem_filter, true_and

      have huniv : A ∪ B = univ := by
        ext v
        simp only [mem_univ, iff_true]
        rw [mem_union, mem_filter, mem_filter]
        simp only [mem_univ, true_and]
        exact hnr v
  4. |A| + |B| = 2m.

    Taking cardinalities on both sides of A ∪ B = univ via `congrArg`, the left-hand side expands to |A| + |B| because A and B are disjoint (`card_union_of_disjoint`), while the right-hand side is the cardinality of Fin (2m), which is 2m by `card_fin`.

    lines 21–24

    uses congrArg, card_union_of_disjoint, card_fin

      have hcard_sum : A.card + B.card = 2 * m := by
        have h1 : (A ∪ B).card = (univ : Finset (Fin (2 * m))).card := congrArg card huniv
        rw [card_union_of_disjoint hdisj, card_fin] at h1
        exact h1
  5. The total sum of out-degrees equals the sum over A plus the sum over B.

    Because A and B form a disjoint partition of the vertex set, the sum of out-degrees across all vertices decomposes into the sum over A plus the sum over B using `sum_union`.

    lines 25–26

    uses sum_union

      have hsum_split : (∑ v, digraph_out_count T v) = (∑ v ∈ A, digraph_out_count T v) + (∑ v ∈ B, digraph_out_count T v) := by
        rw [← huniv, sum_union hdisj]
  6. The sum of out-degrees over A equals |A| * (m - 1).

    Every vertex in A has out-degree m - 1 by definition. Replacing the summand by this constant via `sum_congr`, the sum evaluates to |A| * (m - 1) by `sum_const` and `Nat.nsmul_eq_mul`.

    lines 27–33

    uses sum_congr, mem_filter, sum_const, Nat.nsmul_eq_mul

      have hsum_A : (∑ v ∈ A, digraph_out_count T v) = A.card * (m - 1) := by
        have : (∑ v ∈ A, digraph_out_count T v) = ∑ v ∈ A, (m - 1) := by
          apply sum_congr rfl
          intro x hx
          rw [mem_filter] at hx
          exact hx.2
        rw [this, sum_const, Nat.nsmul_eq_mul]
  7. The sum of out-degrees over B equals |B| * m.

    Every vertex in B has out-degree m by definition. Replacing the summand by this constant via `sum_congr`, the sum evaluates to |B| * m by `sum_const` and `Nat.nsmul_eq_mul`.

    lines 34–40

    uses sum_congr, mem_filter, sum_const, Nat.nsmul_eq_mul

      have hsum_B : (∑ v ∈ B, digraph_out_count T v) = B.card * m := by
        have : (∑ v ∈ B, digraph_out_count T v) = ∑ v ∈ B, m := by
          apply sum_congr rfl
          intro x hx
          rw [mem_filter] at hx
          exact hx.2
        rw [this, sum_const, Nat.nsmul_eq_mul]
  8. |A| * (m - 1) + |B| * m = m * (2m - 1), and 1 ≤ 2m.

    By `tournament_sum_out_count`, the sum of all out-degrees in a tournament on 2m vertices is (2m)(2m - 1) / 2. Canceling the factor of 2 via `Nat.mul_div_cancel_left` reduces this to m(2m - 1). Substituting the sums over A and B yields the degree sum identity. We also record 1 ≤ 2m for the arithmetic cast that follows.

    lines 41–47

    uses tournament_sum_out_count, Nat.mul_div_cancel_left

      have htot := tournament_sum_out_count (2 * m) T hT
      have hdiv : (2 * m) * (2 * m - 1) / 2 = m * (2 * m - 1) := by
        have : (2 * m) * (2 * m - 1) = 2 * (m * (2 * m - 1)) := by ring
        rw [this, Nat.mul_div_cancel_left _ (by decide)]
      rw [hdiv] at htot
      rw [hsum_split, hsum_A, hsum_B] at htot
      have hm2 : 1 ≤ 2 * m := by omega
  9. |A| = m and |B| = m. automation

    We have two linear equations in two unknowns: |A| + |B| = 2m and |A|(m - 1) + |B|m = m(2m - 1). Casting to the integers via `zify` and solving the linear system with `nlinarith` uniquely yields |A| = m and |B| = m.

    lines 48–51

      have hA : A.card = m ∧ B.card = m := by
        zify [hm, hm2] at hcard_sum htot ⊢
        constructor <;> nlinarith
      exact hA
disjoint_filter
Two sub-finsets formed by filtering with predicates p and q are disjoint if and only if no element in the base finset satisfies both p and q.
mem_univ
Every element of a finite type belongs to the universal finset `univ`.
iff_true
The proposition (p ↔ True) simplifies to p.
mem_union
An element belongs to the union s ∪ t if and only if it belongs to s or to t.
mem_filter
An element belongs to the filtered finset filter p s if and only if it belongs to s and satisfies p.
true_and
The proposition True ∧ p simplifies to p.
congrArg
Functions respect equality: if a₁ = a₂, then f a₁ = f a₂.
card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their individual cardinalities.
card_fin
The cardinality of the universal finset of Fin n is n.
sum_union
The sum of a function over the union of two disjoint finsets equals the sum over the first plus the sum over the second.
sum_congr
Two finset sums are equal if their index sets are equal and their summands agree on every element of the index set.
sum_const
Summing a constant value over a finset equals the finset's cardinality scalar-multiplied by that constant.
Nat.nsmul_eq_mul
Scalar multiplication of natural numbers m • n equals their standard multiplication m * n.
tournament_sum_out_count
In any tournament on n vertices, the sum of all out-degrees is n * (n - 1) / 2.
Nat.mul_div_cancel_left
For any positive natural number n, (n * m) / n = m.

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

/-- In a near-regular tournament of order 2m, exactly m vertices have out-degree m - 1 and m vertices have out-degree m. -/theorem tournament_near_regular_card_degrees (m : ℕ) (hm : 1 ≤ m)    (T : Digraph (Fin (2 * m))) [DecidableRel T.Adj] (hT : digraph_is_tournament T)    (hnr : tournament_is_near_regular m T) :    (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 := by  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 huniv : A ∪ B = univ := by    ext v    simp only [mem_univ, iff_true]    rw [mem_union, mem_filter, mem_filter]    simp only [mem_univ, true_and]    exact hnr v  have hcard_sum : A.card + B.card = 2 * m := by    have h1 : (A ∪ B).card = (univ : Finset (Fin (2 * m))).card := congrArg card huniv    rw [card_union_of_disjoint hdisj, card_fin] at h1    exact h1  have hsum_split : (∑ v, digraph_out_count T v) = (∑ v ∈ A, digraph_out_count T v) + (∑ v ∈ B, digraph_out_count T v) := by    rw [← huniv, sum_union hdisj]  have hsum_A : (∑ v ∈ A, digraph_out_count T v) = A.card * (m - 1) := by    have : (∑ v ∈ A, digraph_out_count T v) = ∑ v ∈ A, (m - 1) := by      apply sum_congr rfl      intro x hx      rw [mem_filter] at hx      exact hx.2    rw [this, sum_const, Nat.nsmul_eq_mul]  have hsum_B : (∑ v ∈ B, digraph_out_count T v) = B.card * m := by    have : (∑ v ∈ B, digraph_out_count T v) = ∑ v ∈ B, m := by      apply sum_congr rfl      intro x hx      rw [mem_filter] at hx      exact hx.2    rw [this, sum_const, Nat.nsmul_eq_mul]  have htot := tournament_sum_out_count (2 * m) T hT  have hdiv : (2 * m) * (2 * m - 1) / 2 = m * (2 * m - 1) := by    have : (2 * m) * (2 * m - 1) = 2 * (m * (2 * m - 1)) := by ring    rw [this, Nat.mul_div_cancel_left _ (by decide)]  rw [hdiv] at htot  rw [hsum_split, hsum_A, hsum_B] at htot  have hm2 : 1 ≤ 2 * m := by omega  have hA : A.card = m ∧ B.card = m := by    zify [hm, hm2] at hcard_sum htot ⊢    constructor <;> nlinarith  exact hA
See it in the graphDiscuss this resultChallenge it