tournament_realizes
A tournament T on Fin n realizes degree vector d if T is a tournament and the outdegree of every vertex i equals d i.
Statement
open Classical in def tournament_realizes (n : ℕ) (T : Digraph (Fin n)) (d : Fin n → ℕ) : Prop
- Defined in
- arXiv:2610.40521 Section 2
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 2
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- Used by 1
- tournament_exists_covering_realization_of_realizesLet 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…
Read back from the Lean
Given a natural number n, a directed graph T with vertices in Fin n, and a sequence of target degrees d : Fin n → ℕ, tournament_realizes n T d asserts that T is a tournament and that for every vertex i : Fin n, the out-degree of i in T equals d i.
Specifically, it asserts the conjunction of:
1. T has no self-loops: for all x : Fin n, ¬ T.Adj x x.
2. For all distinct vertices x, y : Fin n (x ≠ y), exactly one directed edge exists between them (T.Adj x y ↔ ¬ T.Adj y x).
3. For every vertex i : Fin n, the number of vertices w : Fin n such that T.Adj i w is equal to d i.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
open Classical in /-- A tournament T on Fin n realizes a degree vector d if T is a tournament and the outdegree of each vertex i equals d(i). -/ def tournament_realizes (n : ℕ) (T : Digraph (Fin n)) (d : Fin n → ℕ) : Prop := digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i