tournament_universal_kings_iff_max_outdegree
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.
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.
constructor · intro hall by_contra hc push Not at hc obtain ⟨w, hw⟩ := hc
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.
uses
tournament_exists_covering_realizationobtain ⟨T, ⟨hT, hdT⟩, hcov⟩ := tournament_exists_covering_realization d hd v w hwThe 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.
uses
tournament_not_king_of_coveredhave hking := hall T ⟨hT, hdT⟩ have hnotking := tournament_not_king_of_covered T hT w v hcov exact hnotking hking
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.
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
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.
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