digraph_apex_over_bidirected_complete_edge_count
D_d has (d + 1)² arcs.
Statement
theorem digraph_apex_over_bidirected_complete_edge_count (d : ℕ)
[DecidableRel (digraph_apex_over_bidirected_complete d).Adj] :
digraph_edge_count (digraph_apex_over_bidirected_complete d) = (d + 1) ^ 2- Source
- Lemma for digraph_min_cut_additive_bound_fails_for_every_d; arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 6.
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_apex_over_bidirected_completeThe digraph D_d on d + 2 vertices: a bidirected complete graph on the vertices 0, …, d, together with an apex d + 1 that sends an arc to…
- digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
- Used by 1
- digraph_min_cut_additive_bound_fails_for_every_dFor every d ≥ 2 there is a loopless digraph with minimum outdegree at least d and m = (d + 1)² arcs in which every vertex bipartition A ⊔…
The proof, explained
The proof counts the arcs of the directed graph D_d by partitioning them by target vertex, so the total count is the sum of the in-degrees over all d + 2 vertices. By definition of the adjacency relation, no arcs point into the apex vertex Fin.last (d + 1), giving it in-degree 0, whereas every other vertex receives an arc from all d + 1 other vertices, giving it in-degree d + 1. Summing 0 for the apex and d + 1 for each of the remaining d + 1 vertices yields (d + 1) * (d + 1) = (d + 1)² arcs.
The apex vertex has in-degree 0, while every other vertex has in-degree d + 1.
For any vertex v in Fin (d + 2), we distinguish whether v is the apex vertex Fin.last (d + 1). If v is the apex, the adjacency condition requires the target to be distinct from the apex, so no arc can enter v; thus the set of in-neighbors is empty and has cardinality 0. If v is not the apex, an arc points from u to v if and only if u ≠ v, meaning the in-neighbors of v are exactly all other vertices, Finset.univ.erase v. The cardinality of this set is |Fin (d + 2)| - 1 = d + 2 - 1 = d + 1.
uses
Finset.card_eq_zero,Finset.filter_eq_empty_iff,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_erase,and_true,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_finhave hfib : ∀ v : Fin (d + 2), (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card = if v = Fin.last (d + 1) then 0 else d + 1 := by intro v split_ifs with hv · rw [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro u _ h exact h.2 hv · have : (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v) = Finset.univ.erase v := by ext u simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true] exact ⟨fun h => h.1, fun h => ⟨h, hv⟩⟩ rw [this, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin] omega
The number of arcs entering a vertex v equals the cardinality of the in-neighborhood of v.
The projection map (u, w) ↦ u gives a bijection between the fiber of arcs whose target is v and the set of in-neighbors of v. Injectivity holds because both pairs have their second coordinate equal to v, and surjectivity holds because for any in-neighbor u of v, the pair (u, v) is an incoming arc.
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_and,Prod.exthave hbij : ∀ v : Fin (d + 2), ((Finset.univ.filter fun p : Fin (d + 2) × Fin (d + 2) => (digraph_apex_over_bidirected_complete d).Adj p.1 p.2).filter (fun p => p.2 = v)).card = (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card := by intro v apply Finset.card_bij (fun p _ => p.1) · intro p hp simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢ rw [← hp.2] exact hp.1 · intro p hp q hq h simp only [Finset.mem_filter] at hp hq exact Prod.ext h (hp.2.trans hq.2.symm) · intro u hu refine ⟨(u, v), ?_, rfl⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu ⊢ exact ⟨hu, by simp⟩
The total arc count equals the sum over all vertices v of their in-degrees.
By definition, digraph_edge_count is the size of the set of all arcs. Partitioning this set by the second coordinate (the target vertex) via Finset.card_eq_sum_card_fiberwise expresses the total count as the sum of fiber sizes over all vertices. Rewriting using the fiber bijection and the in-degree formula turns this into the sum of 0 for the apex and d + 1 for all other vertices.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univunfold digraph_edge_count rw [Finset.card_eq_sum_card_fiberwise (f := Prod.snd) (t := Finset.univ) (fun _ _ => Finset.mem_univ _)] simp only [hbij, hfib]
Evaluating the sum of in-degrees gives (d + 2 - 1) * (d + 1).
We isolate the apex term from the sum using Finset.add_sum_erase. The apex term evaluates to 0 and drops out. On the remaining set Finset.univ.erase (Fin.last (d + 1)), every vertex is distinct from the apex, so each summand is the constant d + 1. Summing this constant over the erased set yields its cardinality times d + 1, where the cardinality is |Fin (d + 2)| - 1 = d + 2 - 1.
uses
Finset.add_sum_erase,Finset.mem_univ,if_pos,zero_add,Finset.sum_congr,if_neg,Finset.ne_of_mem_erase,Finset.sum_const,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_fin,smul_eq_mulrw [← Finset.add_sum_erase _ _ (Finset.mem_univ (Fin.last (d + 1))), if_pos rfl, zero_add, Finset.sum_congr rfl (fun v hv => if_neg (Finset.ne_of_mem_erase hv)), Finset.sum_const, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin, smul_eq_mul]
The total arc count simplifies to (d + 1)².
Linear arithmetic simplifies d + 2 - 1 to d + 1, leaving the expression (d + 1) * (d + 1). Commutative ring arithmetic then confirms this equals (d + 1)².
rw [show d + 2 - 1 = d + 1 by omega] ring
and_true- The conjunction of a proposition with True simplifies to the proposition.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
Finset.add_sum_erase- A finite sum equals the term at a chosen element plus the sum over the set with that element removed.
Finset.card_bij- Two finite sets have equal cardinality if there exists a map between them that is injective and surjective.
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases the set's cardinality by 1.
Finset.card_eq_zero- The cardinality of a finite set is 0 if and only if the set is empty.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum over a target finite set of the cardinalities of its fibers under a map.
Finset.card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.filter_eq_empty_iff- Filtering a finite set by a predicate yields the empty set if and only if no element satisfies the predicate.
Finset.mem_erase- An element belongs to a set with a removed if and only if it is not equal to a and belongs to the original set.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.ne_of_mem_erase- Any element belonging to a set with a removed is distinct from a.
Finset.sum_congr- Two sums over finite sets are equal if their index sets are equal and their summands agree on every element.
Finset.sum_const- Summing a constant over a finite set equals the cardinality of the set multiplied by that constant.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
if_pos- An if-then-else expression evaluates to the then-branch when the condition is true.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
smul_eq_mul- Scalar multiplication of natural numbers coincides with ordinary multiplication.
true_and- The conjunction of True with a proposition simplifies to the proposition.
zero_add- Adding zero on the left is the identity: 0 + a = a.
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.
theorem digraph_apex_over_bidirected_complete_edge_count (d : ℕ) [DecidableRel (digraph_apex_over_bidirected_complete d).Adj] : digraph_edge_count (digraph_apex_over_bidirected_complete d) = (d + 1) ^ 2 := by have hfib : ∀ v : Fin (d + 2), (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card = if v = Fin.last (d + 1) then 0 else d + 1 := by intro v split_ifs with hv · rw [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro u _ h exact h.2 hv · have : (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v) = Finset.univ.erase v := by ext u simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_erase, and_true] exact ⟨fun h => h.1, fun h => ⟨h, hv⟩⟩ rw [this, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin] omega have hbij : ∀ v : Fin (d + 2), ((Finset.univ.filter fun p : Fin (d + 2) × Fin (d + 2) => (digraph_apex_over_bidirected_complete d).Adj p.1 p.2).filter (fun p => p.2 = v)).card = (Finset.univ.filter fun u => (digraph_apex_over_bidirected_complete d).Adj u v).card := by intro v apply Finset.card_bij (fun p _ => p.1) · intro p hp simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp ⊢ rw [← hp.2] exact hp.1 · intro p hp q hq h simp only [Finset.mem_filter] at hp hq exact Prod.ext h (hp.2.trans hq.2.symm) · intro u hu refine ⟨(u, v), ?_, rfl⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu ⊢ exact ⟨hu, by simp⟩ unfold digraph_edge_count rw [Finset.card_eq_sum_card_fiberwise (f := Prod.snd) (t := Finset.univ) (fun _ _ => Finset.mem_univ _)] simp only [hbij, hfib] rw [← Finset.add_sum_erase _ _ (Finset.mem_univ (Fin.last (d + 1))), if_pos rfl, zero_add, Finset.sum_congr rfl (fun v hv => if_neg (Finset.ne_of_mem_erase hv)), Finset.sum_const, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin, smul_eq_mul] rw [show d + 2 - 1 = d + 1 by omega] ring