tournament_strong_king_iff_in_neighbor_out_degree_le
In 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 u to v) satisfies d⁺(u) ≤ d⁺(v).
Statement
theorem tournament_strong_king_iff_in_neighbor_out_degree_le {V : Type*} [Fintype V] (T : Digraph V) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (v : V) : tournament_is_strong_king T v ↔ ∀ u, T.Adj u v → digraph_out_degree T u ≤ digraph_out_degree T v
- Formalizes
- arXiv:2610.39702 Lemma 2.4 -- Quantum Query Complexity of Tournament Solutions
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_two_path_diff_eq_out_degree_diffIn any finite tournament T, if there is an arc from u to v, then the difference between the number of directed two-paths from v to u and…
- digraph_two_path_countThe number of directed paths of length two from u to v in a finite directed graph D, defined as the number of vertices w such that D has…
- 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_max_out_degree_is_strong_kingIn any finite tournament T, every vertex v of maximum out-degree is a strong king.
Read back from the Lean
Let $V$ be a finite type, and let $T$ be a directed graph on $V$ with a decidable adjacency relation. Assume that $T$ is a tournament (meaning it has no self-loops and for every pair of distinct vertices $x \neq y$, exactly one of the directed edges $(x, y)$ or $(y, x)$ is present). Then, for any vertex $v \in V$, $v$ is a strong king in $T$ (meaning that for every in-neighbor $u$ of $v$, the number of directed 2-paths from $u$ to $v$ is strictly less than the number of directed 2-paths from $v$ to $u$) if and only if for every in-neighbor $u$ of $v$, the out-degree of $u$ in $T$ is less than or equal to the out-degree of $v$ in $T$.
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 relies on the algebraic identity p₂(v, u) - p₂(u, v) = d⁺(v) - d⁺(u) + 1, valid for any arc u → v in a tournament. A vertex v is a strong king precisely when p₂(u, v) < p₂(v, u) for all in-neighbors u, which means the difference p₂(v, u) - p₂(u, v) is at least 1. By the identity, this occurs if and only if d⁺(v) - d⁺(u) ≥ 0, which is equivalent to d⁺(u) ≤ d⁺(v).
The equivalence reduces to proving the forward and backward implications separately.
We enable classical logic and split the bi-implication into two subgoals: the forward direction (a strong king has out-degree at least that of each in-neighbor) and the reverse direction (the out-degree condition implies the vertex is a strong king).
classical constructorIf v is a strong king, then every in-neighbor u of v satisfies d⁺(u) ≤ d⁺(v).
Let v be a strong king and let u be an in-neighbor (u → v). By definition of a strong king, there are strictly fewer 2-paths from u to v than from v to u, so p₂(v, u) - p₂(u, v) ≥ 1 in ℤ. Applying the identity `tournament_two_path_diff_eq_out_degree_diff` expresses this difference as (d⁺(v) - d⁺(u)) + 1. Linear integer arithmetic (`omega`) then deduces d⁺(u) ≤ d⁺(v), which is cast back from ℤ to ℕ.
uses
tournament_two_path_diff_eq_out_degree_diff· intro hk u huv have h := tournament_two_path_diff_eq_out_degree_diff T hT huv have h' : (digraph_two_path_count T u v : ℤ) < (digraph_two_path_count T v u : ℤ) := by exact_mod_cast hk u huv have h2 : (digraph_out_degree T u : ℤ) ≤ (digraph_out_degree T v : ℤ) := by omega exact_mod_cast h2
If every in-neighbor u of v satisfies d⁺(u) ≤ d⁺(v), then v is a strong king.
Conversely, assume d⁺(u) ≤ d⁺(v) for every in-neighbor u of v, and let u be an in-neighbor. By `tournament_two_path_diff_eq_out_degree_diff`, the difference in 2-paths is p₂(v, u) - p₂(u, v) = (d⁺(v) - d⁺(u)) + 1. Because d⁺(u) ≤ d⁺(v), the term d⁺(v) - d⁺(u) is non-negative, making the difference at least 1. Linear integer arithmetic (`omega`) deduces p₂(u, v) < p₂(v, u), and casting back to ℕ establishes that v is a strong king.
uses
tournament_two_path_diff_eq_out_degree_diff· intro hk u huv have h := tournament_two_path_diff_eq_out_degree_diff T hT huv have h2 : (digraph_out_degree T u : ℤ) ≤ (digraph_out_degree T v : ℤ) := by exact_mod_cast hk u huv have h3 : (digraph_two_path_count T u v : ℤ) < (digraph_two_path_count T v u : ℤ) := by omega exact_mod_cast h3
tournament_two_path_diff_eq_out_degree_diff- In any finite tournament T, if there is a directed arc from u to v, then the difference between the number of directed 2-paths from v to u and from u to v equals (d⁺(v) - d⁺(u)) + 1.
- The proof casts degrees and two-path counts from ℕ to ℤ so that their differences can be manipulated algebraically without underflow at zero; `exact_mod_cast` moves hypotheses and goals between ℤ and ℕ.
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.
/-- A vertex in a finite tournament is a strong king if and only if every in-neighbor has out-degree at most its out-degree. -/theorem tournament_strong_king_iff_in_neighbor_out_degree_le {V : Type*} [Fintype V] (T : Digraph V) [DecidableRel T.Adj] (hT : digraph_is_tournament T) (v : V) : tournament_is_strong_king T v ↔ ∀ u, T.Adj u v → digraph_out_degree T u ≤ digraph_out_degree T v := by classical constructor · intro hk u huv have h := tournament_two_path_diff_eq_out_degree_diff T hT huv have h' : (digraph_two_path_count T u v : ℤ) < (digraph_two_path_count T v u : ℤ) := by exact_mod_cast hk u huv have h2 : (digraph_out_degree T u : ℤ) ≤ (digraph_out_degree T v : ℤ) := by omega exact_mod_cast h2 · intro hk u huv have h := tournament_two_path_diff_eq_out_degree_diff T hT huv have h2 : (digraph_out_degree T u : ℤ) ≤ (digraph_out_degree T v : ℤ) := by exact_mod_cast hk u huv have h3 : (digraph_two_path_count T u v : ℤ) < (digraph_two_path_count T v u : ℤ) := by omega exact_mod_cast h3