tournament_not_near_regular_exists_extreme_degree
In 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.
Statement
theorem tournament_not_near_regular_exists_extreme_degree (m : ℕ) (hm : 1 ≤ m)
(T : Digraph (Fin (2 * m))) [DecidableRel T.Adj]
(hnr : ¬ tournament_is_near_regular m T) :
(∃ v : Fin (2 * m), m + 1 ≤ digraph_out_count T v) ∨
(∃ v : Fin (2 * m), digraph_out_count T v ≤ m - 2)- Source
- step towards even_tournament_arborescence_maximizer_is_near_regular
- Verified
- 28 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.
The proof, explained
By definition, a tournament on 2m vertices is near-regular when every vertex has out-degree m - 1 or m. Negating this definition gives a vertex v whose out-degree is neither m - 1 nor m. Case analysis on whether this out-degree is at most m - 2 immediately provides a witness for the second disjunct in the affirmative case, or for the first disjunct (out-degree at least m + 1) in the negative case by simple integer arithmetic.
There exists a vertex v whose out-degree is neither m - 1 nor m.
Unfolding the definition of near-regularity (`tournament_is_near_regular`) in the hypothesis `hnr` that T is not near-regular, and distributing the negation through the universal quantifier and disjunction using `not_forall` and `not_or`, produces a vertex v satisfying ¬(out-degree = m - 1) and ¬(out-degree = m).
uses
tournament_is_near_regular,not_forall,not_orsimp only [tournament_is_near_regular, not_forall, not_or] at hnr obtain ⟨v, hv1, hv2⟩ := hnr
If the out-degree of v is at most m - 2, the second disjunct of the theorem holds.
We split into cases on whether the out-degree of v is at most m - 2 (`by_cases`). In the affirmative case, v directly witnesses the existence of a vertex with out-degree at most m - 2, satisfying the right disjunct via `Or.inr`.
uses
Or.inrby_cases h : digraph_out_count T v ≤ m - 2 · exact Or.inr ⟨v, h⟩
If the out-degree of v exceeds m - 2, the first disjunct of the theorem holds.
In the remaining case, the out-degree of v is not at most m - 2. Since it is an integer that also cannot equal m - 1 or m, linear arithmetic (`omega`) deduces that the out-degree must be at least m + 1. Vertex v thus witnesses the left disjunct via `Or.inl`.
uses
Or.inl· exact Or.inl ⟨v, by omega⟩
tournament_is_near_regular- a tournament on 2m vertices is near-regular if every vertex has out-degree m - 1 or m
not_forall- the negation of a universal statement is equivalent to the existence of a counterexample: ¬(∀ x, p x) ↔ ∃ x, ¬p x
not_or- the negation of a disjunction is equivalent to the conjunction of the negations: ¬(p ∨ q) ↔ ¬p ∧ ¬q
Or.inr- a disjunction a ∨ b holds if the right disjunct b holds
Or.inl- a disjunction a ∨ b holds if the left disjunct a holds
- The hypotheses that $T$ is a tournament (rather than an arbitrary directed graph) and that $1 \le m$ are part of the theorem statement but are not needed for this step of the deduction.
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 tournament of order 2m that is not near-regular has at least one vertex of out-degree >= m + 1 or out-degree <= m - 2. -/theorem tournament_not_near_regular_exists_extreme_degree (m : ℕ) (hm : 1 ≤ m) (T : Digraph (Fin (2 * m))) [DecidableRel T.Adj] (hnr : ¬ tournament_is_near_regular m T) : (∃ v : Fin (2 * m), m + 1 ≤ digraph_out_count T v) ∨ (∃ v : Fin (2 * m), digraph_out_count T v ≤ m - 2) := by simp only [tournament_is_near_regular, not_forall, not_or] at hnr obtain ⟨v, hv1, hv2⟩ := hnr by_cases h : digraph_out_count T v ≤ m - 2 · exact Or.inr ⟨v, h⟩ · exact Or.inl ⟨v, by omega⟩