threshold_loopless_digraph_ge_one
For every natural number n and every threshold degree sequence d on n vertices, there exists at least one loopless digraph with in-degree and out-degree equal to d, so D(d) ≥ 1.
Statement
theorem threshold_loopless_digraph_ge_one (n : ℕ) (d : Fin n → ℕ) (h : is_threshold_sequence d) : 1 ≤ loopless_digraph_count d- Source
- arXiv:2611.02191 Sec. 1.1; Csikvari and Imolay (2020)
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_threshold_sequenceA degree sequence d on n vertices is a threshold degree sequence if there exists a simple graph G on n vertices with degree sequence d…
- loopless_digraph_countFor a degree sequence d on n vertices, D(d) is the number of loopless digraphs on n vertices in which every vertex v has both in-degree…
- Used by 1
- threshold_loopless_digraph_twoFor every threshold degree sequence d on 2 vertices, the number of loopless digraphs with in-degree and out-degree equal to d is 1.
Read back from the Lean
For any natural number n and any degree sequence d : Fin n → ℕ, if d is a threshold sequence (i.e., the degree sequence of a simple graph on Fin n having no induced 2K₂, C₄, or P₄), then the number of loopless directed graphs on vertex set Fin n whose in-degree and out-degree at each vertex v are both equal to d v is at least 1.
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
By definition, a threshold degree sequence $d$ is realized by an undirected simple graph $G$ whose vertex degrees match $d$. We convert $G$ into a directed graph by placing directed edges in both directions along every undirected edge. Because $G$ is loopless and undirected, this symmetric digraph has no self-loops, and each vertex's in-degree and out-degree both equal its undirected degree in $G$. This digraph provides an explicit witness, showing that the count of valid loopless digraph realizations is at least 1.
There exists an undirected simple graph $G$ on Fin $n$ such that every vertex $v$ has $\deg_G(v) = d(v)$.
We unpack the hypothesis that $d$ is a threshold sequence (`is_threshold_sequence`), which by definition ensures the existence of an underlying simple graph $G$ whose degree sequence matches $d$. Classical logic is enabled for decidability of predicates.
classical rcases h with ⟨G, -, hdeg⟩
To show $1 \le \mathrm{loopless\_digraph\_count}(d)$, it suffices to show that the digraph whose directed edges are given by the adjacency relation of $G$ is a valid realization.
We unfold the definition of `loopless_digraph_count`, which counts the valid loopless digraph realizations of $d$. Rewriting $1 \le |S|$ as $0 < |S|$ and observing that any nonempty finite set has positive cardinality, the problem reduces to providing a single valid digraph realization. We propose the symmetric digraph whose directed edges are precisely the edges of $G$.
uses
Nat.succ_le_iff,Finset.card_pos.2unfold loopless_digraph_count rw [Nat.succ_le_iff] apply Finset.card_pos.2 refine ⟨⟨G.Adj⟩, ?_⟩
It suffices to verify three conditions for the symmetric digraph: it has no self-loops, every vertex has out-degree $d(v)$, and every vertex has in-degree $d(v)$.
By definition of set filtering, an element belongs to the set of realizations if it is in the universal set of digraphs and satisfies the three defining properties. Membership in the universal set is immediate, leaving the three properties as subgoals.
uses
Finset.mem_filter,Finset.mem_univrw [Finset.mem_filter] refine ⟨Finset.mem_univ _, ?_⟩ refine ⟨?_, ?_, ?_⟩
The digraph has no self-loops: for every vertex $v$, $\neg G.\mathrm{Adj}(v, v)$.
For any vertex $v$, simple graphs contain no self-loops by definition, as their adjacency relation is irreflexive (`G.irrefl`).
uses
G.irrefl· intro v exact G.irrefl
For every vertex $v$, its out-degree in the digraph equals $d(v)$.
The set of out-neighbors of $v$, $\{w \mid G.\mathrm{Adj}(v, w)\}$, is identical to the open neighborhood $N(v)$ of $v$ in $G$. The cardinality of $N(v)$ is by definition the degree $\deg_G(v)$, which equals $d(v)$ by our choice of $G$.
uses
SimpleGraph.card_neighborFinset_eq_degree· intro v have h1 : (Finset.univ.filter (fun w => G.Adj v w)) = G.neighborFinset v := by ext w; simp rw [h1, SimpleGraph.card_neighborFinset_eq_degree, hdeg v]
For every vertex $v$, its in-degree in the digraph equals $d(v)$.
The set of in-neighbors of $v$, $\{u \mid G.\mathrm{Adj}(u, v)\}$, is also identical to $N(v)$ because adjacency in a simple graph is symmetric ($G.\mathrm{Adj}(u, v) \leftrightarrow G.\mathrm{Adj}(v, u)$). Its cardinality is therefore $\deg_G(v) = d(v)$.
uses
G.adj_comm,SimpleGraph.card_neighborFinset_eq_degree· intro v have h1 : (Finset.univ.filter (fun u => G.Adj u v)) = G.neighborFinset v := by ext u; simp [G.adj_comm] rw [h1, SimpleGraph.card_neighborFinset_eq_degree, hdeg v]
Nat.succ_le_iff- For natural numbers $m$ and $n$, $m + 1 \le n$ if and only if $m < n$. Here used with $m = 0$ to turn $1 \le |S|$ into $0 < |S|$.
Finset.card_pos.2- A finite set has strictly positive cardinality if it is nonempty.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filter predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
G.irrefl- Adjacency in a simple graph is irreflexive: no vertex is adjacent to itself ($\neg G.\mathrm{Adj}(v, v)$).
SimpleGraph.card_neighborFinset_eq_degree- The number of neighbors of a vertex $v$ in a simple graph equals its degree $\deg_G(v)$.
G.adj_comm- Adjacency in a simple graph is symmetric: $G.\mathrm{Adj}(u, v) \leftrightarrow G.\mathrm{Adj}(v, u)$.
- While the definition of `is_threshold_sequence` requires the graph to avoid certain induced subgraphs ($2K_2$, $C_4$, and $P_4$), the proof only uses the existence of a simple graph whose degree sequence is $d$.
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.
/-- Every threshold degree sequence has at least one loopless digraph realization, namely its symmetric realization. -/theorem threshold_loopless_digraph_ge_one (n : ℕ) (d : Fin n → ℕ) (h : is_threshold_sequence d) : 1 ≤ loopless_digraph_count d := by classical rcases h with ⟨G, -, hdeg⟩ unfold loopless_digraph_count rw [Nat.succ_le_iff] apply Finset.card_pos.2 refine ⟨⟨G.Adj⟩, ?_⟩ rw [Finset.mem_filter] refine ⟨Finset.mem_univ _, ?_⟩ refine ⟨?_, ?_, ?_⟩ · intro v exact G.irrefl · intro v have h1 : (Finset.univ.filter (fun w => G.Adj v w)) = G.neighborFinset v := by ext w; simp rw [h1, SimpleGraph.card_neighborFinset_eq_degree, hdeg v] · intro v have h1 : (Finset.univ.filter (fun u => G.Adj u v)) = G.neighborFinset v := by ext u; simp [G.adj_comm] rw [h1, SimpleGraph.card_neighborFinset_eq_degree, hdeg v]