tournament_not_king_of_covered
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
- tournament_universal_kings_iff_max_outdegreeFor every realizable degree vector d of an n-vertex tournament and every vertex v, v is a king in every tournament realizing d if and only…
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.
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).
intro h obtain ⟨hwv, hcovx⟩ := hcov
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.
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
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.
rcases h w hwv_ne with hvw | ⟨x, hvx, hxw⟩
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.
· exact (htour v w hv_ne_w).mp hvw hwvThe 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.
· 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
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.
/-- 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