AFTD Auto-Formalizing Theoretical Domains

tournament_not_near_regular_exists_extreme_degree

theoremverified

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

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.

  1. 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).

    lines 7–8

    uses tournament_is_near_regular, not_forall, not_or

      simp only [tournament_is_near_regular, not_forall, not_or] at hnr
      obtain ⟨v, hv1, hv2⟩ := hnr
  2. 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`.

    lines 9–10

    uses Or.inr

      by_cases h : digraph_out_count T v ≤ m - 2
      · exact Or.inr ⟨v, h⟩
  3. 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`.

    line 11

    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

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it