AFTD Auto-Formalizing Theoretical Domains

tournament_max_out_degree_is_strong_king

theoremverifiedformalization

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.

  1. 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.

    line 3

    uses tournament_strong_king_iff_in_neighbor_out_degree_le

      exact (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

/-- 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)
See it in the graphDiscuss this resultChallenge it