threshold_loopless_digraph_two
For every threshold degree sequence d on 2 vertices, the number of loopless digraphs with in-degree and out-degree equal to d is 1.
Statement
theorem threshold_loopless_digraph_two (d : Fin 2 → ℕ) (h : is_threshold_sequence d) : loopless_digraph_count d = 1- Related work
- arXiv:2611.02191 Sec. 11.2
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- threshold_loopless_digraph_ge_oneFor every natural number n and every threshold degree sequence d on n vertices, there exists at least one loopless digraph with in-degree…
Read back from the Lean
For any function $d : \text{Fin } 2 \to \mathbb{N}$, if $d$ is a threshold sequence (meaning there exists a simple graph on $\text{Fin } 2$ with no induced $2K_2$, $C_4$, or $P_4$ whose vertex degrees equal $d$), then the number of loopless directed graphs on $\text{Fin } 2$ where each vertex $v$ has both out-degree and in-degree equal to $d(v)$ is $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
For every threshold degree sequence d on 2 vertices, the general existence theorem threshold_loopless_digraph_ge_one guarantees at least one realizing loopless digraph. Because self-loops are forbidden, the only possible edges on {0, 1} are 0 → 1 and 1 → 0, and the specified out-degrees d(0) and d(1) completely determine whether each of these two directed edges is present. Consequently, any two realizing digraphs must have identical adjacency relations, which bounds the count above by 1 and forces the total count to be exactly 1.
The set of out-neighbors of vertex 0 in a loopless digraph D on {0, 1} is {1} if 0 → 1 is an edge, and ∅ otherwise.
By set extensionality, we evaluate membership for each element of Fin 2. For vertex 0, self-loops are ruled out by the loopless hypothesis hloop 0, and 0 is neither in {1} nor in ∅. For vertex 1, 1 is an out-neighbor of 0 if and only if D.Adj 0 1 holds, which matches the condition for 1 to belong to {1}.
ext x fin_cases x · split_ifs <;> simp [hloop 0] · split_ifs <;> simp [*]
The set of out-neighbors of vertex 1 in a loopless digraph D on {0, 1} is {0} if 1 → 0 is an edge, and ∅ otherwise.
By set extensionality, we test both vertices in Fin 2. Vertex 0 is an out-neighbor of 1 exactly when D.Adj 1 0 holds, matching membership in {0}. Vertex 1 cannot be an out-neighbor of itself by hloop 1, and 1 belongs to neither {0} nor ∅.
ext x fin_cases x · split_ifs <;> simp [*] · split_ifs <;> simp [hloop 1]
The out-degree of vertex 0 in D is 1 if 0 → 1 is an edge, and 0 otherwise.
Rewriting the out-neighborhood of vertex 0 with threshold_loopless_digraph_two_filter_zero, its cardinality is |{1}| = 1 if D.Adj 0 1 holds, and |∅| = 0 otherwise.
uses
threshold_loopless_digraph_two_filter_zerorw [threshold_loopless_digraph_two_filter_zero D hloop] split_ifs <;> simp
The out-degree of vertex 1 in D is 1 if 1 → 0 is an edge, and 0 otherwise.
Rewriting the out-neighborhood of vertex 1 with threshold_loopless_digraph_two_filter_one, its cardinality is |{0}| = 1 if D.Adj 1 0 holds, and |∅| = 0 otherwise.
uses
threshold_loopless_digraph_two_filter_onerw [threshold_loopless_digraph_two_filter_one D hloop] split_ifs <;> simp
Vertex 0 is adjacent to vertex 1 if and only if d(0) = 1.
Substituting the formula for the out-degree of 0 from threshold_loopless_digraph_two_card_zero into the degree assumption gives (if D.Adj 0 1 then 1 else 0) = d 0. For the forward implication, if D.Adj 0 1 holds, if_pos simplifies the left-hand side to 1, showing d 0 = 1. For the reverse implication, assuming d 0 = 1 and supposing for contradiction ¬D.Adj 0 1, if_neg reduces the left-hand side to 0, which contradicts d 0 = 1.
uses
threshold_loopless_digraph_two_card_zero,if_pos,if_negrw [threshold_loopless_digraph_two_card_zero D hloop] at hdeg constructor · intro h rw [if_pos h] at hdeg exact hdeg.symm · intro h by_contra hc rw [if_neg hc] at hdeg omega
Vertex 1 is adjacent to vertex 0 if and only if d(1) = 1.
Substituting the out-degree formula from threshold_loopless_digraph_two_card_one gives (if D.Adj 1 0 then 1 else 0) = d 1. If D.Adj 1 0 holds, if_pos reduces this to 1 = d 1. Conversely, if d 1 = 1 and we assume for contradiction ¬D.Adj 1 0, if_neg reduces the equation to 0 = d 1, which contradicts d 1 = 1.
uses
threshold_loopless_digraph_two_card_one,if_pos,if_negrw [threshold_loopless_digraph_two_card_one D hloop] at hdeg constructor · intro h rw [if_pos h] at hdeg exact hdeg.symm · intro h by_contra hc rw [if_neg hc] at hdeg omega
Any two loopless digraphs D1 and D2 on {0, 1} with the same out-degree sequence d are identical.
We decompose D1 and D2 into their underlying adjacency relations A1 and A2. By extensionality, it suffices to show A1 u v ↔ A2 u v for all pairs (u, v) in {0, 1}². Loops (0, 0) and (1, 1) are false in both digraphs by the loopless hypotheses hloop1 and hloop2. The off-diagonal edges A1 0 1 and A2 0 1 are both equivalent to d 0 = 1 by threshold_loopless_digraph_two_adj_zero_one, hence to each other; similarly, A1 1 0 and A2 1 0 are both equivalent to d 1 = 1 by threshold_loopless_digraph_two_adj_one_zero. Thus A1 = A2, and substituting this equality yields D1 = D2.
uses
threshold_loopless_digraph_two_adj_zero_one,threshold_loopless_digraph_two_adj_one_zerorcases D1 with ⟨A1⟩ rcases D2 with ⟨A2⟩ have heq : A1 = A2 := by ext u v fin_cases u <;> fin_cases v · have hl1 := hloop1 0; have hl2 := hloop2 0; tauto · have h1 := threshold_loopless_digraph_two_adj_zero_one d ⟨A1⟩ hloop1 (hdeg1 0) have h2 := threshold_loopless_digraph_two_adj_zero_one d ⟨A2⟩ hloop2 (hdeg2 0) exact h1.trans h2.symm · have h1 := threshold_loopless_digraph_two_adj_one_zero d ⟨A1⟩ hloop1 (hdeg1 1) have h2 := threshold_loopless_digraph_two_adj_one_zero d ⟨A2⟩ hloop2 (hdeg2 1) exact h1.trans h2.symm · have hl1 := hloop1 1; have hl2 := hloop2 1; tauto rw [heq]
At least one loopless digraph has degree sequence d (loopless_digraph_count d ≥ 1).
We invoke the general theorem threshold_loopless_digraph_ge_one for n = 2, which establishes that every threshold degree sequence admits at least one realizing loopless digraph.
uses
threshold_loopless_digraph_ge_oneclassical have hge : 1 ≤ loopless_digraph_count d := threshold_loopless_digraph_ge_one 2 d hAt most one loopless digraph has degree sequence d (loopless_digraph_count d ≤ 1).
Unfolding loopless_digraph_count and applying Finset.card_le_one_iff, it suffices to show any two members D1 and D2 of the filtered set of realizing digraphs are equal. By Finset.mem_filter, each digraph is loopless and has out-degree sequence d. The uniqueness lemma threshold_loopless_digraph_two_digraph_eq then shows D1 = D2.
uses
Finset.card_le_one_iff,Finset.mem_filter,threshold_loopless_digraph_two_digraph_eqhave hle : loopless_digraph_count d ≤ 1 := by unfold loopless_digraph_count rw [Finset.card_le_one_iff] intro D1 D2 h1 h2 rw [Finset.mem_filter] at h1 h2 exact threshold_loopless_digraph_two_digraph_eq d D1 D2 h1.2.1 h1.2.2.1 h2.2.1 h2.2.2.1
The number of loopless digraphs with degree sequence d is exactly 1.
Combining the lower bound 1 ≤ loopless_digraph_count d and the upper bound loopless_digraph_count d ≤ 1, linear arithmetic over ℕ (via omega) closes the goal.
omega
threshold_loopless_digraph_two_filter_zero- In a loopless digraph on two vertices, the set of out-neighbors of vertex 0 is {1} if 0 is adjacent to 1, and the empty set ∅ otherwise.
threshold_loopless_digraph_two_filter_one- In a loopless digraph on two vertices, the set of out-neighbors of vertex 1 is {0} if 1 is adjacent to 0, and the empty set ∅ otherwise.
threshold_loopless_digraph_two_card_zero- In a loopless digraph on two vertices, the out-degree of vertex 0 is 1 if 0 is adjacent to 1, and 0 otherwise.
threshold_loopless_digraph_two_card_one- In a loopless digraph on two vertices, the out-degree of vertex 1 is 1 if 1 is adjacent to 0, and 0 otherwise.
if_pos- If a proposition c is true, then the conditional if c then t else e evaluates to t.
if_neg- If a proposition c is false, then the conditional if c then t else e evaluates to e.
threshold_loopless_digraph_two_adj_zero_one- In a loopless digraph on two vertices whose out-degree at vertex 0 is d(0), vertex 0 is adjacent to vertex 1 if and only if d(0) = 1.
threshold_loopless_digraph_two_adj_one_zero- In a loopless digraph on two vertices whose out-degree at vertex 1 is d(1), vertex 1 is adjacent to vertex 0 if and only if d(1) = 1.
threshold_loopless_digraph_two_digraph_eq- Any two loopless digraphs on two vertices having the same out-degree sequence d are equal.
threshold_loopless_digraph_ge_one- For every threshold degree sequence d on n vertices, there is at least one loopless digraph with degree sequence d.
Finset.card_le_one_iff- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p.
- In Lean, a Digraph is represented as a structure wrapping an adjacency relation Adj : V → V → Prop, so proving two digraphs are equal reduces directly to proving their adjacency relations are equal by function extensionality.
- Although the definition of loopless_digraph_count requires both in-degrees and out-degrees to match the given sequence d, on two vertices the out-degrees alone uniquely determine the digraph, so the in-degree hypotheses are not needed in threshold_loopless_digraph_two_digraph_eq.
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.
open scoped Classical inlemma threshold_loopless_digraph_two_filter_zero (D : Digraph (Fin 2)) (hloop : ∀ v, ¬ D.Adj v v) : (Finset.univ.filter (fun w => D.Adj 0 w)) = if D.Adj 0 1 then {1} else ∅ := by ext x fin_cases x · split_ifs <;> simp [hloop 0] · split_ifs <;> simp [*]open scoped Classical inlemma threshold_loopless_digraph_two_filter_one (D : Digraph (Fin 2)) (hloop : ∀ v, ¬ D.Adj v v) : (Finset.univ.filter (fun w => D.Adj 1 w)) = if D.Adj 1 0 then {0} else ∅ := by ext x fin_cases x · split_ifs <;> simp [*] · split_ifs <;> simp [hloop 1]open scoped Classical inlemma threshold_loopless_digraph_two_card_zero (D : Digraph (Fin 2)) (hloop : ∀ v, ¬ D.Adj v v) : (Finset.univ.filter (fun w => D.Adj 0 w)).card = if D.Adj 0 1 then 1 else 0 := by rw [threshold_loopless_digraph_two_filter_zero D hloop] split_ifs <;> simpopen scoped Classical inlemma threshold_loopless_digraph_two_card_one (D : Digraph (Fin 2)) (hloop : ∀ v, ¬ D.Adj v v) : (Finset.univ.filter (fun w => D.Adj 1 w)).card = if D.Adj 1 0 then 1 else 0 := by rw [threshold_loopless_digraph_two_filter_one D hloop] split_ifs <;> simpopen scoped Classical inlemma threshold_loopless_digraph_two_adj_zero_one (d : Fin 2 → ℕ) (D : Digraph (Fin 2)) (hloop : ∀ v, ¬ D.Adj v v) (hdeg : (Finset.univ.filter (fun w => D.Adj 0 w)).card = d 0) : D.Adj 0 1 ↔ d 0 = 1 := by rw [threshold_loopless_digraph_two_card_zero D hloop] at hdeg constructor · intro h rw [if_pos h] at hdeg exact hdeg.symm · intro h by_contra hc rw [if_neg hc] at hdeg omegaopen scoped Classical inlemma threshold_loopless_digraph_two_adj_one_zero (d : Fin 2 → ℕ) (D : Digraph (Fin 2)) (hloop : ∀ v, ¬ D.Adj v v) (hdeg : (Finset.univ.filter (fun w => D.Adj 1 w)).card = d 1) : D.Adj 1 0 ↔ d 1 = 1 := by rw [threshold_loopless_digraph_two_card_one D hloop] at hdeg constructor · intro h rw [if_pos h] at hdeg exact hdeg.symm · intro h by_contra hc rw [if_neg hc] at hdeg omegaopen scoped Classical inlemma threshold_loopless_digraph_two_digraph_eq (d : Fin 2 → ℕ) (D1 D2 : Digraph (Fin 2)) (hloop1 : ∀ v, ¬ D1.Adj v v) (hdeg1 : ∀ v, (Finset.univ.filter (fun w => D1.Adj v w)).card = d v) (hloop2 : ∀ v, ¬ D2.Adj v v) (hdeg2 : ∀ v, (Finset.univ.filter (fun w => D2.Adj v w)).card = d v) : D1 = D2 := by rcases D1 with ⟨A1⟩ rcases D2 with ⟨A2⟩ have heq : A1 = A2 := by ext u v fin_cases u <;> fin_cases v · have hl1 := hloop1 0; have hl2 := hloop2 0; tauto · have h1 := threshold_loopless_digraph_two_adj_zero_one d ⟨A1⟩ hloop1 (hdeg1 0) have h2 := threshold_loopless_digraph_two_adj_zero_one d ⟨A2⟩ hloop2 (hdeg2 0) exact h1.trans h2.symm · have h1 := threshold_loopless_digraph_two_adj_one_zero d ⟨A1⟩ hloop1 (hdeg1 1) have h2 := threshold_loopless_digraph_two_adj_one_zero d ⟨A2⟩ hloop2 (hdeg2 1) exact h1.trans h2.symm · have hl1 := hloop1 1; have hl2 := hloop2 1; tauto rw [heq]/-- For n = 2, every threshold degree sequence has D(d) = 1. -/theorem threshold_loopless_digraph_two (d : Fin 2 → ℕ) (h : is_threshold_sequence d) : loopless_digraph_count d = 1 := by classical have hge : 1 ≤ loopless_digraph_count d := threshold_loopless_digraph_ge_one 2 d h have hle : loopless_digraph_count d ≤ 1 := by unfold loopless_digraph_count rw [Finset.card_le_one_iff] intro D1 D2 h1 h2 rw [Finset.mem_filter] at h1 h2 exact threshold_loopless_digraph_two_digraph_eq d D1 D2 h1.2.1 h1.2.2.1 h2.2.1 h2.2.2.1 omega