AFTD Auto-Formalizing Theoretical Domains

tournament_degree_vector_realizable

def

A degree vector d on Fin n is realizable if there exists a tournament T on Fin n whose outdegrees are given by d.

Statement

open Classical in
def tournament_degree_vector_realizable (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.

Read back from the Lean

Given a natural number $n$ and a function $d : \mathrm{Fin}\ n \to \mathbb{N}$, this definition asserts that there exists a directed graph $T$ with vertices $\mathrm{Fin}\ n$ such that: 1. $T$ is a tournament: it has no self-loops ($\forall x, \neg T.\mathrm{Adj}(x, x)$), and for all distinct vertices $x \neq y$, exactly one of the directed edges $(x, y)$ or $(y, x)$ exists ($T.\mathrm{Adj}(x, y) \leftrightarrow \neg T.\mathrm{Adj}(y, x)$). 2. For every vertex $i : \mathrm{Fin}\ n$, the out-degree of $i$ in $T$ (the number of vertices $w : \mathrm{Fin}\ n$ such that $T.\mathrm{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 degree vector d on Fin n is realizable if there exists an n-vertex tournament whose outdegrees match d. -/
def tournament_degree_vector_realizable (n : ℕ) (d : Fin n → ℕ) : Prop := ∃ T : Digraph (Fin n), digraph_is_tournament T ∧ ∀ i : Fin n, digraph_out_count T i = d i
See it in the graphDiscuss this resultChallenge it