AFTD Auto-Formalizing Theoretical Domains

tournament_universal_kings_iff_max_outdegree

theoremverifiedformalization

For every realizable degree vector d of an n-vertex tournament and every vertex v, v is a king in every tournament realizing d if and only if v has maximum outdegree according to d (that is, d u ≤ d v for all vertices u).

Statement

open Classical in
theorem tournament_universal_kings_iff_max_outdegree (n : ℕ) (d : Fin n → ℕ)
    (hd : ∃ T : Digraph (Fin n), digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i)
    (v : Fin n) :
    (∀ T : Digraph (Fin n), (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) →
      (∀ u, u ≠ v → T.Adj v u ∨ ∃ w, T.Adj v w ∧ T.Adj w u)) ↔
      ∀ u : Fin n, d u ≤ d v
Formalizes
arXiv:2610.40521 Corollary 7
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • tournament_not_king_of_coveredIf a vertex w covers another vertex v in a tournament T (that is, w -> v and w -> x for every out-neighbor x of v), then v is not a king…
  • tournament_is_king_of_max_outdegreeIn every tournament on n vertices, every vertex of maximum outdegree is a king: every other vertex is reachable from it by a directed path…
  • tournament_exists_covering_realizationLet d be a realizable degree vector of an n-vertex tournament, and let v, w be vertices satisfying d v < d w. Then there exists a…
  • 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.

Read back from the Lean

Under classical logic, given a natural number $n$, a degree sequence $d : \mathrm{Fin}\ n \to \mathbb{N}$, a hypothesis that there exists at least one tournament $T$ on vertex set $\mathrm{Fin}\ n$ whose out-degree at each vertex $i$ is $d(i)$, and a fixed vertex $v : \mathrm{Fin}\ n$: $v$ is a king in every tournament with score sequence $d$ (that is, for every directed graph $T$ on $\mathrm{Fin}\ n$, if $T$ is a tournament and the out-degree of every vertex $i$ in $T$ equals $d(i)$, then for every vertex $u \neq v$, either there is a directed edge from $v$ to $u$ or there exists a vertex $w$ with directed edges from $v$ to $w$ and from $w$ to $u$) if and only if $v$ has maximum out-degree in $d$ (that is, for all $u : \mathrm{Fin}\ n$, $d(u) \le d(v)$).

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 equivalence is established in two directions. For the forward direction, if a universal king v did not have maximum outdegree, there would be a vertex w with strictly larger outdegree, allowing the construction of a tournament realizing d where w covers v; but a covered vertex cannot be a king, which produces a contradiction. For the backward direction, if v has maximum outdegree under d, then v has maximum outdegree in every tournament realizing d, and every vertex of maximum outdegree in a tournament is a king.

  1. To prove the forward direction by contradiction, assume v is a king in every realization of d, and obtain a vertex w such that d v < d w.

    The equivalence is split into two directions. In the forward direction, we assume that v is a king in every tournament realizing d. For contradiction, suppose v does not have maximum outdegree under d. Negating this universal statement provides a vertex w whose outdegree strictly exceeds that of v, so d v < d w.

    lines 9–13

      constructor
      · intro hall
        by_contra hc
        push Not at hc
        obtain ⟨w, hw⟩ := hc
  2. There exists a tournament T realizing d in which w covers v.

    By tournament_exists_covering_realization, because d is realizable and d v < d w, there exists a tournament T with outdegree sequence d in which w beats v and every out-neighbor of v is also an out-neighbor of w.

    line 14

    uses tournament_exists_covering_realization

        obtain ⟨T, ⟨hT, hdT⟩, hcov⟩ := tournament_exists_covering_realization d hd v w hw
  3. The covering tournament contradicts the hypothesis that v is a universal king, completing the forward direction.

    Since T realizes d, the hypothesis that v is a universal king implies that v must be a king in T. On the other hand, tournament_not_king_of_covered shows that because w covers v in T, v cannot be a king in T. These contradictory assertions complete the proof of the forward direction by contradiction.

    lines 15–17

    uses tournament_not_king_of_covered

        have hking := hall T ⟨hT, hdT⟩
        have hnotking := tournament_not_king_of_covered T hT w v hcov
        exact hnotking hking
  4. In the backward direction, if v has maximum outdegree under d, then v is a king in every tournament realizing d.

    Assume d u ≤ d v for all vertices u, and let T be any tournament realizing d. By tournament_is_king_of_max_outdegree, it suffices to show that v has maximum outdegree in T. Because the outdegrees in T equal the values of d, this inequality holds directly from the assumption on d.

    lines 18–22

    uses tournament_is_king_of_max_outdegree

      · intro hmax T ⟨hT, hdT⟩
        apply tournament_is_king_of_max_outdegree T hT v
        intro u
        rw [hdT u, hdT v]
        exact hmax u
tournament_exists_covering_realization
If a tournament degree vector d is realizable and d v < d w, then there exists a tournament realizing d in which w covers v (meaning w beats v, and every out-neighbor of v is also an out-neighbor of w).
tournament_not_king_of_covered
In any tournament, if a vertex w covers a vertex v, then v is not a king.
tournament_is_king_of_max_outdegree
In any tournament, any vertex of maximum outdegree is a king (every other vertex can be reached from it in at most two steps).

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

open Classical in/-- The universal kings of a realizable tournament degree vector are exactly the vertices of maximum outdegree. -/theorem tournament_universal_kings_iff_max_outdegree (n : ℕ) (d : Fin n → ℕ)    (hd : ∃ T : Digraph (Fin n), digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i)    (v : Fin n) :    (∀ T : Digraph (Fin n), (digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i) →      (∀ u, u ≠ v → T.Adj v u ∨ ∃ w, T.Adj v w ∧ T.Adj w u)) ↔      ∀ u : Fin n, d u ≤ d v := by  constructor  · intro hall    by_contra hc    push Not at hc    obtain ⟨w, hw⟩ := hc    obtain ⟨T, ⟨hT, hdT⟩, hcov⟩ := tournament_exists_covering_realization d hd v w hw    have hking := hall T ⟨hT, hdT⟩    have hnotking := tournament_not_king_of_covered T hT w v hcov    exact hnotking hking  · intro hmax T ⟨hT, hdT⟩    apply tournament_is_king_of_max_outdegree T hT v    intro u    rw [hdT u, hdT v]    exact hmax u
See it in the graphDiscuss this resultChallenge it