AFTD Auto-Formalizing Theoretical Domains

tournament_strong_king_iff_in_neighbor_out_degree_le

theoremverifiedformalization

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

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

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

    lines 3–4

      classical
      constructor
  2. If 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 ℕ.

    lines 5–10

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

    lines 11–16

    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.

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

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