AFTD Auto-Formalizing Theoretical Domains

threshold_loopless_digraph_ge_one

theoremverified

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.

  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.

    lines 3–4

      classical
      rcases h with ⟨G, -, hdeg⟩
  2. 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$.

    lines 5–8

    uses Nat.succ_le_iff, Finset.card_pos.2

      unfold loopless_digraph_count
      rw [Nat.succ_le_iff]
      apply Finset.card_pos.2
      refine ⟨⟨G.Adj⟩, ?_⟩
  3. 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.

    lines 9–11

    uses Finset.mem_filter, Finset.mem_univ

      rw [Finset.mem_filter]
      refine ⟨Finset.mem_univ _, ?_⟩
      refine ⟨?_, ?_, ?_⟩
  4. 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`).

    lines 12–13

    uses G.irrefl

      · intro v
        exact G.irrefl
  5. 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$.

    lines 14–17

    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]
  6. 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)$.

    lines 18–21

    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)$.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it