tournament_near_regular_card_degrees
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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.
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)
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.
uses
disjoint_filterhave hdisj : Disjoint A B := by rw [disjoint_filter] intro x _ h1 h2 have : m - 1 ≠ m := by omega exact this (h1.symm.trans h2)
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`).
uses
mem_univ,iff_true,mem_union,mem_filter,true_andhave 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
|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`.
uses
congrArg,card_union_of_disjoint,card_finhave 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
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`.
uses
sum_unionhave 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]
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`.
uses
sum_congr,mem_filter,sum_const,Nat.nsmul_eq_mulhave 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]
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`.
uses
sum_congr,mem_filter,sum_const,Nat.nsmul_eq_mulhave 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]
|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.
uses
tournament_sum_out_count,Nat.mul_div_cancel_lefthave 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
|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.
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.
- The algebraic solution of the system of two equations |A| + |B| = 2m and |A|(m - 1) + |B|m = m(2m - 1) is delegated to automation: `zify` casts the equations from ℕ to ℤ using the bounds 1 ≤ m and 1 ≤ 2m, and `nlinarith` solves for |A| = m and |B| = 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
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.
/-- 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