tournament_exists_covering_realization_of_realizes
Let d be a degree vector on Fin n realized by a tournament T, and let v, w be vertices in Fin n satisfying d v < d w. Then there exists a tournament T' on Fin n realizing d in which w covers v.
Statement
open Classical in theorem tournament_exists_covering_realization_of_realizes {n : ℕ} (d : Fin n → ℕ) (T : Digraph (Fin n)) (hT : tournament_realizes n T d) (v w : Fin n) (hvw : d v < d w) : ∃ T' : Digraph (Fin n), tournament_realizes n T' d ∧ tournament_covers T' w v
- Formalizes
- arXiv:2610.40521 Lemma 6 -- Directed Cut-Query Complexity of Finding a King
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- tournament_realizesA tournament T on Fin n realizes degree vector d if T is a tournament and the outdegree of every vertex i equals d i.
- tournament_coversA vertex w covers a vertex v in a tournament T if w -> v and w -> x for every out-neighbor x of v.
- tournament_exists_covering_realizationLet d be a realizable degree vector of an n-vertex tournament, and let v, w be vertices satisfying d v < d w. Then there exists a…
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- 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 $n$ be a natural number, $d : \text{Fin } n \to \mathbb{N}$ a prescribed out-degree sequence, and $T$ a directed graph on $\text{Fin } n$ that realizes $d$ as a tournament (meaning $T$ is loopless, has exactly one directed edge between any pair of distinct vertices, and every vertex $i$ has out-degree $d(i)$). Let $v, w : \text{Fin } n$ be vertices such that $d(v) < d(w)$. Then there exists a directed graph $T'$ on $\text{Fin } n$ such that: 1. $T'$ also realizes $d$ as a tournament, and 2. $w$ covers $v$ in $T'$, meaning there is a directed edge from $w$ to $v$ in $T'$, and for every vertex $x : \text{Fin } n$, if there is a directed edge from $v$ to $x$, then there is also a directed edge from $w$ to $x$ (i.e., the out-neighborhood of $v$ is a subset of the out-neighborhood of $w$).
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 theorem is a corollary of tournament_exists_covering_realization, which asserts the same result under an existential hypothesis rather than an explicit tournament. The proof constructs an existential witness from the provided tournament T and its realization hypothesis hT, and then directly applies tournament_exists_covering_realization.
There exists a tournament T' realizing the degree sequence d such that w covers v.
The given tournament T and the hypothesis hT (that T realizes d) are packaged into the existential witness ⟨T, hT⟩ demonstrating that d is realizable by a tournament. Applying tournament_exists_covering_realization to this witness and the hypothesis d v < d w immediately yields the desired tournament T'.
uses
tournament_exists_covering_realization∃ T' : Digraph (Fin n), tournament_realizes n T' d ∧ tournament_covers T' w v := tournament_exists_covering_realization d ⟨T, hT⟩ v w hvw
tournament_exists_covering_realization- If a degree sequence d is realizable by some tournament on Fin n, and vertices v, w satisfy d v < d w, then there exists a tournament realizing d in which w covers v.
- The proof is a single term; Lean definitionally unfolds `tournament_realizes` and `tournament_covers` to match the statement of `tournament_exists_covering_realization`.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
open Classical in/-- A tournament realizing degree vector d can be modified to another tournament realizing d in which w covers v, provided d v < d w. -/theorem tournament_exists_covering_realization_of_realizes {n : ℕ} (d : Fin n → ℕ) (T : Digraph (Fin n)) (hT : tournament_realizes n T d) (v w : Fin n) (hvw : d v < d w) : ∃ T' : Digraph (Fin n), tournament_realizes n T' d ∧ tournament_covers T' w v := tournament_exists_covering_realization d ⟨T, hT⟩ v w hvw