tournament_near_regular_of_card_degrees
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
- tournament_is_near_regularA tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m.
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- Used by 1
- tournament_not_near_regular_exists_arc_degree_gapIn a tournament on 2m vertices with m ≥ 2 that is not near-regular, there are vertices u, v with an arc u → v and out-degree of v at least…
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.
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.
uses
Nat.eq_zero_or_pos,Fin.elim0intro v rcases Nat.eq_zero_or_pos m with rfl | hm · exact Fin.elim0 v
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.
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)
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.
uses
card_union_of_disjointhave hcard : (A ∪ B).card = 2 * m := by rw [card_union_of_disjoint hdisj, hdeg.1, hdeg.2] omega
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.
uses
eq_univ_of_card,Fintype.card_finhave huniv : A ∪ B = univ := by apply eq_univ_of_card rw [hcard, Fintype.card_fin]
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.
uses
mem_univhave hv : v ∈ A ∪ B := by rw [huniv] exact mem_univ v
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.
uses
mem_union,mem_filter,Or.inl,Or.inrrw [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.
- The case m = 0 is treated as a degenerate boundary case where the vertex type Fin(0) is empty.
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.
/-- 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