tournament_is_near_regular
def
A tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m.
Statement
def tournament_is_near_regular (m : ℕ) (D : Digraph (Fin (2 * m))) [DecidableRel D.Adj] : Prop
- Defined in
- J.W. Moon, Topics on Tournaments (1968), Section 3
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- Used by 8
- tournament_near_regular_of_card_degreesIf 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.
- tournament_near_regular_card_degreesIn 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.
- exists_near_regular_tournament_fourThere exists a near-regular tournament on 4 vertices.
- tournament_four_not_near_regular_exists_improvingThe m = 2 case of the target, settled by finite computation: a non-near-regular tournament on 4 vertices has at most 9 arborescences while…
- exists_not_near_regular_tournament_fourThere exists a tournament on 4 vertices that is not near-regular.
- tournament_four_arborescence_maximizer_is_near_regularEvery tournament on 4 vertices maximizing the total number of spanning arborescences among all tournaments on 4 vertices is near-regular.
- 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…
- tournament_not_near_regular_exists_extreme_degreeIn any tournament on 2m vertices with m ≥ 1 that is not near-regular, there exists a vertex with out-degree ≥ m + 1 or out-degree ≤ m - 2.
Read back from the Lean
A definition stating that for a natural number m, a directed graph D on vertex set Fin (2 * m), and decidable adjacency on D: for every vertex v : Fin (2 * m), the out-degree of v in D is equal to m - 1 or equal to m.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m. -/ def tournament_is_near_regular (m : ℕ) (D : Digraph (Fin (2 * m))) [DecidableRel D.Adj] : Prop := ∀ v : Fin (2 * m), digraph_out_count D v = m - 1 ∨ digraph_out_count D v = m