AFTD Auto-Formalizing Theoretical Domains

tournament_not_king_of_covered

theoremverifiedformalization

If a vertex w covers another vertex v in a tournament T (that is, w -> v and w -> x for every out-neighbor x of v), then v is not a king in T.

Statement

theorem tournament_not_king_of_covered {V : Type*} (T : Digraph V)
    (hT : digraph_is_tournament T) (w v : V)
    (hcov : T.Adj w v ∧ ∀ x, T.Adj v x → T.Adj w x) :
    ¬ (∀ u, u ≠ v → T.Adj v u ∨ ∃ w', T.Adj v w' ∧ T.Adj w' u)
Formalizes
arXiv:2610.40521 Observation 4
Verified
31 Oct 2026
Axioms
none — Lean reports it depends on no axioms
Built on 1
  • 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 type, $T$ a directed graph on $V$, and $w, v \in V$ vertices. Assume that: 1. $T$ is a tournament (it is loopless, and for all distinct vertices $x, y \in V$, exactly one of the directed edges between them exists), and 2. There is a directed edge from $w$ to $v$, and every out-neighbor of $v$ is also an out-neighbor of $w$ (i.e., for all $x \in V$, if $T.\mathrm{Adj}(v, x)$ then $T.\mathrm{Adj}(w, x)$). Then $v$ is not a king in $T$; that is, it is false that for every vertex $u \in V$ with $u \neq v$, either there is a directed edge from $v$ to $u$, or there exists some vertex $w' \in V$ with directed edges from $v$ to $w'$ and from $w'$ 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 proceeds by contradiction: suppose v is a king in the tournament T. Since w covers v, there is an edge w → v, so w and v are distinct. Applying the king property of v to w, v must be able to reach w in at most two steps: either directly (v → w) or via an intermediate vertex x (v → x → w). The direct edge v → w immediately contradicts w → v by tournament asymmetry, while the two-step path implies w → x (since w covers v), which likewise contradicts x → w.

  1. Assume for contradiction that v is a king, and unpack the covering hypothesis.

    To prove that v is not a king, we assume for contradiction that v can reach every other vertex in at most two steps. From the hypothesis that w covers v, we extract the direct edge w → v (hwv) and the condition that every out-neighbor of v is also an out-neighbor of w (hcovx).

    lines 6–7

      intro h
      obtain ⟨hwv, hcovx⟩ := hcov
  2. The tournament is irreflexive and asymmetric, which implies w ≠ v and v ≠ w.

    From the definition of a tournament, we extract irreflexivity (no vertex has a self-loop) and asymmetry (for any distinct vertices, an edge exists in exactly one direction). Because there is an edge w → v, w cannot equal v, as that would yield a self-loop v → v. Symmetrically, v ≠ w.

    lines 8–11

      have hirr : ∀ x, ¬ T.Adj x x := hT.1
      have htour : ∀ x y, x ≠ y → (T.Adj x y ↔ ¬ T.Adj y x) := hT.2
      have hwv_ne : w ≠ v := fun heq => hirr v (heq ▸ hwv)
      have hv_ne_w : v ≠ w := fun heq => hwv_ne heq.symm
  3. Either v → w or there is an intermediate vertex x such that v → x and x → w.

    Applying the king hypothesis for v to the vertex w (which is distinct from v), v must reach w in at most two steps: either by a direct edge v → w, or via a two-step path through some vertex x.

    line 12

      rcases h w hwv_ne with hvw | ⟨x, hvx, hxw⟩
  4. The direct edge v → w is impossible.

    Since v ≠ w, the tournament condition implies that v → w and w → v cannot both hold. Thus, the direct edge v → w contradicts the assumed edge w → v.

    line 13

      · exact (htour v w hv_ne_w).mp hvw hwv
  5. The two-step path v → x → w is also impossible, completing the proof.

    In the two-step case, we have v → x and x → w. Because w covers v, the edge v → x implies w → x. Furthermore, x ≠ w because x → w would otherwise be a self-loop. By the tournament property on the distinct vertices x and w, x → w and w → x cannot both hold, providing the final contradiction.

    lines 14–16

      · have hwx : T.Adj w x := hcovx x hvx
        have hx_ne_w : x ≠ w := fun heq => hirr x (heq ▸ hxw)
        exact (htour x w hx_ne_w).mp hxw hwx

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

/-- If a vertex w covers v in a tournament T, then v is not a king in T. -/theorem tournament_not_king_of_covered {V : Type*} (T : Digraph V)    (hT : digraph_is_tournament T) (w v : V)    (hcov : T.Adj w v ∧ ∀ x, T.Adj v x → T.Adj w x) :    ¬ (∀ u, u ≠ v → T.Adj v u ∨ ∃ w', T.Adj v w' ∧ T.Adj w' u) := by  intro h  obtain ⟨hwv, hcovx⟩ := hcov  have hirr : ∀ x, ¬ T.Adj x x := hT.1  have htour : ∀ x y, x ≠ y → (T.Adj x y ↔ ¬ T.Adj y x) := hT.2  have hwv_ne : w ≠ v := fun heq => hirr v (heq ▸ hwv)  have hv_ne_w : v ≠ w := fun heq => hwv_ne heq.symm  rcases h w hwv_ne with hvw | ⟨x, hvx, hxw⟩  · exact (htour v w hv_ne_w).mp hvw hwv  · have hwx : T.Adj w x := hcovx x hvx    have hx_ne_w : x ≠ w := fun heq => hirr x (heq ▸ hxw)    exact (htour x w hx_ne_w).mp hxw hwx
See it in the graphDiscuss this resultChallenge it