tournament_max_out_degree_is_strong_king
In any finite tournament T, every vertex v of maximum out-degree is a strong king.
Statement
theorem tournament_max_out_degree_is_strong_king {V : Type*} [Fintype V] (T : Digraph V) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (v : V) (hmax : ∀ u, digraph_out_degree T u ≤ digraph_out_degree T v) : tournament_is_strong_king T v
- Formalizes
- arXiv:2610.39702 Lemma 2.5 -- Quantum Query Complexity of Tournament Solutions
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- tournament_is_strong_kingA vertex v in a finite directed graph D is a strong king if for every in-neighbor u of v (that is, every vertex u with an arc from u to…
- digraph_out_degreeThe out-degree d⁺(v) of a vertex v in a finite directed graph D is the number of out-neighbors of v, that is, the cardinality of the set…
- tournament_strong_king_iff_in_neighbor_out_degree_leIn any finite tournament T, a vertex v is a strong king if and only if every in-neighbor u of v (that is, every vertex u with an arc from…
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
Read back from the Lean
Let $V$ be a finite type and $T$ be a directed graph on $V$ with decidable adjacency relation. Assume that $T$ is a tournament (i.e., it has no self-loops, and for all distinct $x, y \in V$, exactly one of $T.Adj\ x\ y$ or $T.Adj\ y\ x$ holds). Let $v \in V$ be a vertex such that for every $u \in V$, the out-degree of $u$ in $T$ is at most the out-degree of $v$ in $T$. Then $v$ is a strong king in $T$: for every $u \in V$ such that there is a directed edge from $u$ to $v$ ($T.Adj\ u\ v$), the number of directed two-paths from $u$ to $v$ is strictly less than the number of directed two-paths from $v$ to $u$.
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 proof reduces the claim to an established characterization: in any tournament, a vertex is a strong king if and only if its out-degree is at least that of each of its in-neighbors. Because v has maximum out-degree among all vertices in the tournament, this condition holds trivially for all in-neighbors of v.
The vertex v is a strong king in the tournament T.
By tournament_strong_king_iff_in_neighbor_out_degree_le, a vertex v in a tournament is a strong king if and only if every in-neighbor u of v satisfies out-deg(u) ≤ out-deg(v). By assumption (hmax), v has maximum out-degree among all vertices in T, so out-deg(u) ≤ out-deg(v) holds for all vertices u, and in particular for every in-neighbor of v. Applying the reverse direction of the equivalence completes the proof.
uses
tournament_strong_king_iff_in_neighbor_out_degree_leexact (tournament_strong_king_iff_in_neighbor_out_degree_le T hT v).mpr (fun u _ => hmax u)
tournament_strong_king_iff_in_neighbor_out_degree_le- In a tournament, a vertex is a strong king if and only if every in-neighbor has out-degree less than or equal to that of the vertex.
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.
/-- Every vertex of maximum out-degree in a tournament is a strong king. -/theorem tournament_max_out_degree_is_strong_king {V : Type*} [Fintype V] (T : Digraph V) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (v : V) (hmax : ∀ u, digraph_out_degree T u ≤ digraph_out_degree T v) : tournament_is_strong_king T v := by exact (tournament_strong_king_iff_in_neighbor_out_degree_le T hT v).mpr (fun u _ => hmax u)