digraph_edge_count_eq_sum_outdegrees
The number of arcs of a finite digraph equals the sum of its outdegrees.
Statement
theorem digraph_edge_count_eq_sum_outdegrees {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] : digraph_edge_count G = ∑ v, (Finset.univ.filter (G.Adj v)).card
- Source
- Helper for digraph_both_cuts_ge_ceil_div_six_of_indegree_lt, arXiv:2610.21381, proof of Theorem 1.4, Case 2. The two-partition certificate and paired-outcome inequality are a deterministic formulation of the paper's averaging argument; no research advance is claimed.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
- Used by 2
- digraph_outdegree_three_mul_le_edge_countIn a finite loopless digraph of minimum outdegree at least two, three times any vertex outdegree is at most the total number of arcs.
- digraph_edge_count_eq_sum_indegreesThe number of arcs of a finite digraph equals the sum of its indegrees.
The proof, explained
The theorem is proved by rewriting the total edge count as a double sum over all pairs of vertices. By definition, the number of edges is the number of pairs (x, y) satisfying G.Adj x y. Expressing this count as a sum of indicators and decomposing the Cartesian product of vertices into nested sums produces an outer sum over x and an inner sum over y. Finally, the inner sum is identified as the cardinality of the out-neighborhood of x (its outdegree), showing that the sum of all outdegrees equals the total number of edges.
The total edge count of the digraph is rewritten as the iterated sum ∑ x, ∑ y, (if G.Adj x y then 1 else 0).
By definition, `digraph_edge_count G` is the cardinality of the set of vertex pairs (x, y) that form an edge in G. Rewriting with `Finset.card_filter` expresses this cardinality as a sum of indicator values over all pairs in the universal set V × V. Applying `Finset.univ_product_univ` in reverse identifies the universal set of pairs with the Cartesian product of the vertex set with itself, and `Finset.sum_product` converts this sum over pairs into a double sum over x and y.
uses
Finset.card_filter,Finset.univ_product_univ,Finset.sum_productunfold digraph_edge_count rw [Finset.card_filter, ← Finset.univ_product_univ, Finset.sum_product]
The inner sum over y is recognized as the outdegree of x, completing the proof.
On the right-hand side, the outdegree of each vertex v is defined as the cardinality of its out-neighborhood {y ∈ V | G.Adj v y}. Applying `Finset.card_filter` converts each such cardinality into the sum of indicator values ∑ y, (if G.Adj v y then 1 else 0). Since evaluating the edge predicate on the pair (x, y) simplifies to G.Adj x y, both sides become identical.
uses
Finset.card_filtersimp only [Finset.card_filter]
Finset.card_filter- The number of elements in a filtered finite set {i ∈ s | p i} equals the sum over i ∈ s of the indicator function (1 if p i holds, 0 otherwise).
Finset.univ_product_univ- The Cartesian product of the universal finset on α and the universal finset on β is the universal finset on the product type α × β.
Finset.sum_product- A sum of a function over a Cartesian product of two finite sets s ×ˢ t equals the iterated sum over s and then over t: ∑ x ∈ s ×ˢ t, f x = ∑ x ∈ s, ∑ y ∈ t, f (x, y).
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_edge_count_eq_sum_outdegrees {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] : digraph_edge_count G = ∑ v, (Finset.univ.filter (G.Adj v)).card := by unfold digraph_edge_count rw [Finset.card_filter, ← Finset.univ_product_univ, Finset.sum_product] simp only [Finset.card_filter]