tournament_is_king_of_max_outdegree
In every tournament on n vertices, every vertex of maximum outdegree is a king: every other vertex is reachable from it by a directed path of length at most two.
Statement
open Classical in theorem tournament_is_king_of_max_outdegree {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T) (v : Fin n) (hmax : ∀ u : Fin n, digraph_out_count T u ≤ digraph_out_count T v) : ∀ u, u ≠ v → T.Adj v u ∨ ∃ w, T.Adj v w ∧ T.Adj w u
- Formalizes
- arXiv:2610.40521 Equation 2
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- Used by 1
- tournament_universal_kings_iff_max_outdegreeFor 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…
Read back from the Lean
For every natural number n, directed graph T with vertices Fin n, and vertex v : Fin n, if T is a tournament (meaning T has no self-loops, and for all distinct vertices x and y, there is an edge from x to y if and only if there is no edge from y to x), and if v has maximum out-degree in T (for every vertex u : Fin n, the number of vertices w such that T.Adj u w is at most the number of vertices w such that T.Adj v w), then for every vertex u : Fin n distinct from v, either there is a directed edge from v to u, or there exists an intermediate vertex w : Fin n such that there are directed edges from v to w and from w to u (i.e., v is a king).
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
We argue by contradiction: suppose a vertex v of maximum outdegree cannot reach some vertex u in at most two steps. Then u must dominate v, and every out-neighbor of v must also be dominated by u (otherwise v could reach u in two steps via that out-neighbor). Consequently, the out-neighborhood of u contains v along with the entire out-neighborhood of v. Since tournaments have no self-loops, this forces u to have strictly greater outdegree than v, contradicting the maximality of v's outdegree.
Assume for contradiction that some vertex u ≠ v is not reachable from v by a directed path of length at most two, and unpack the tournament hypotheses.
We fix a vertex u ≠ v and assume for contradiction that v cannot reach u in one step (¬T.Adj v u) and cannot reach u in two steps via any intermediate vertex w (if T.Adj v w then ¬T.Adj w u). We also unpack the tournament hypothesis into irreflexivity (no vertex has a self-loop) and the tournament condition (for any two distinct vertices, exactly one directed edge connects them).
intro u huv by_contra h push Not at h obtain ⟨hv_ne_u, hcover⟩ := h obtain ⟨hirr, htour⟩ := hT
There is a directed arc from u to v.
Since u ≠ v and there is no arc from v to u, the tournament condition requires that the directed arc must run from u to v (T.Adj u v).
have huv_arc : T.Adj u v := (htour u v huv).mpr hv_ne_uEvery out-neighbor of v is also an out-neighbor of u.
Let x be an out-neighbor of v (T.Adj v x). First, x cannot equal u because that would mean T.Adj v u, which we assumed is false. Second, since T.Adj v x and v cannot reach u in two steps, there cannot be an arc from x to u (¬T.Adj x u). By the tournament condition applied to distinct vertices u and x, ¬T.Adj x u implies an arc from u to x (T.Adj u x).
have hcovx : ∀ x, T.Adj v x → T.Adj u x := by intro x hvx have hxu : x ≠ u := by intro hx; subst hx; exact hv_ne_u hvx exact (htour u x hxu.symm).mpr (hcover x hvx)
The set {v} ∪ N⁺(v) is a subset of N⁺(u).
For any x in {v} ∪ N⁺(v), either x = v or x ∈ N⁺(v). If x = v, we have T.Adj u v from the earlier step. If x ∈ N⁺(v), then T.Adj u x because every out-neighbor of v is an out-neighbor of u. Thus in both cases x is an out-neighbor of u.
uses
Finset.mem_insert,Finset.mem_filter,Finset.mem_univ,true_andhave hsub : (insert v (Finset.univ.filter (fun w => T.Adj v w))) ⊆ (Finset.univ.filter (fun w => T.Adj u w)) := by intro x hx simp only [Finset.mem_insert, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ rcases hx with rfl | hvx · exact huv_arc · exact hcovx x hvx
The vertex v is not in its own out-neighborhood.
By the irreflexivity of the tournament, there is no self-loop T.Adj v v, so v does not belong to the set of out-neighbors of v.
have hnotmem : v ∉ Finset.univ.filter (fun w => T.Adj v w) := by simp [hirr v]
|N⁺(v)| + 1 ≤ |N⁺(u)|.
Because {v} ∪ N⁺(v) ⊆ N⁺(u), the subset has cardinality at most |N⁺(u)| by Finset.card_le_card. Since v ∉ N⁺(v), inserting v increases the cardinality of N⁺(v) by 1 via Finset.card_insert_of_notMem, yielding |N⁺(v)| + 1 ≤ |N⁺(u)|.
uses
Finset.card_le_card,Finset.card_insert_of_notMemhave hcard : (Finset.univ.filter (fun w => T.Adj v w)).card + 1 ≤ (Finset.univ.filter (fun w => T.Adj u w)).card := by have := Finset.card_le_card hsub rw [Finset.card_insert_of_notMem hnotmem] at this exact this
A contradiction is reached against the maximality of the outdegree of v.
By the maximality assumption on v, the outdegree of u is at most that of v (|N⁺(u)| ≤ |N⁺(v)|). Unfolding the definition of outdegree (digraph_out_count) produces an immediate linear integer arithmetic contradiction with |N⁺(v)| + 1 ≤ |N⁺(u)|, which omega closes.
uses
digraph_out_counthave hle := hmax u simp only [digraph_out_count] at hle omega
Finset.mem_insert- An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The conjunction True ∧ p is equivalent to p.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_insert_of_notMem- Inserting an element a into a finset s not containing a yields a set of cardinality |s| + 1.
digraph_out_count- The outdegree of a vertex v in a directed graph is defined as the cardinality of its out-neighborhood {w | T.Adj v w}.
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/-- In any tournament on Fin n, every vertex of maximum outdegree is a king. -/theorem tournament_is_king_of_max_outdegree {n : ℕ} (T : Digraph (Fin n)) (hT : digraph_is_tournament T) (v : Fin n) (hmax : ∀ u : Fin n, digraph_out_count T u ≤ digraph_out_count T v) : ∀ u, u ≠ v → T.Adj v u ∨ ∃ w, T.Adj v w ∧ T.Adj w u := by intro u huv by_contra h push Not at h obtain ⟨hv_ne_u, hcover⟩ := h obtain ⟨hirr, htour⟩ := hT have huv_arc : T.Adj u v := (htour u v huv).mpr hv_ne_u have hcovx : ∀ x, T.Adj v x → T.Adj u x := by intro x hvx have hxu : x ≠ u := by intro hx; subst hx; exact hv_ne_u hvx exact (htour u x hxu.symm).mpr (hcover x hvx) have hsub : (insert v (Finset.univ.filter (fun w => T.Adj v w))) ⊆ (Finset.univ.filter (fun w => T.Adj u w)) := by intro x hx simp only [Finset.mem_insert, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ rcases hx with rfl | hvx · exact huv_arc · exact hcovx x hvx have hnotmem : v ∉ Finset.univ.filter (fun w => T.Adj v w) := by simp [hirr v] have hcard : (Finset.univ.filter (fun w => T.Adj v w)).card + 1 ≤ (Finset.univ.filter (fun w => T.Adj u w)).card := by have := Finset.card_le_card hsub rw [Finset.card_insert_of_notMem hnotmem] at this exact this have hle := hmax u simp only [digraph_out_count] at hle omega