digraph_edge_count_eq_sum_indegrees
The number of arcs of a finite digraph equals the sum of its indegrees.
Statement
theorem digraph_edge_count_eq_sum_indegrees {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] : digraph_edge_count G = ∑ v, (Finset.univ.filter fun u => G.Adj u 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 2
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
- digraph_edge_count_eq_sum_outdegreesThe number of arcs of a finite digraph equals the sum of its outdegrees.
The proof, explained
The proof reduces the theorem to the equality between the sum of out-degrees and the sum of in-degrees using the known edge-count identity `digraph_edge_count_eq_sum_outdegrees`. Each degree count is expressed as a sum of indicator functions via `Finset.card_filter`, turning both sides into double sums over all pairs of vertices. Swapping the order of summation using `Finset.sum_comm` then closes the goal.
The edge count is replaced by the sum of out-degrees, reducing the theorem to showing that the sum of out-degrees equals the sum of in-degrees.
By `digraph_edge_count_eq_sum_outdegrees`, the total number of edges in $G$ equals the sum of all out-degrees, $\\sum_v |\\{u \\mid G.\\text{Adj}(v, u)\\}|$. Rewriting the left-hand side with this identity reduces the goal to showing that the total out-degree equals the total in-degree, $\\sum_v |\\{u \\mid G.\\text{Adj}(u, v)\\}|$.
uses
digraph_edge_count_eq_sum_outdegreesrw [digraph_edge_count_eq_sum_outdegrees]Both sums are rewritten as double sums of indicator functions over all vertex pairs.
Using `Finset.card_filter`, the cardinality of each filtered set is expressed as a sum of indicator values: $|\\{i \\in s \\mid p(i)\\}| = \\sum_{i \\in s} (\\text{if } p(i) \\text{ then } 1 \\text{ else } 0)$. This rewrites the sum of out-degrees as $\\sum_x \\sum_i (\\text{if } G.\\text{Adj}(x, i) \\text{ then } 1 \\text{ else } 0)$ and the sum of in-degrees as $\\sum_x \\sum_i (\\text{if } G.\\text{Adj}(i, x) \\text{ then } 1 \\text{ else } 0)$.
uses
Finset.card_filtersimp only [Finset.card_filter]The sum of out-degrees equals the sum of in-degrees.
Applying `Finset.sum_comm` exchanges the order of summation in the double sum, which directly equates the out-degree indicator sum to the in-degree indicator sum and concludes the proof.
uses
Finset.sum_commexact Finset.sum_comm
digraph_edge_count_eq_sum_outdegrees- The number of edges in a finite digraph equals the sum of the out-degrees of all vertices.
Finset.card_filter- The cardinality of the subset of elements in a finite set satisfying a predicate equals the sum over that set of the predicate's indicator function: $|\\{i \\in s \\mid p(i)\\}| = \\sum_{i \\in s} (\\text{if } p(i) \\text{ then } 1 \\text{ else } 0)$.
Finset.sum_comm- The order of summation in a finite double sum can be swapped: $\\sum_{x \\in s} \\sum_{y \\in t} f(x, y) = \\sum_{y \\in t} \\sum_{x \\in s} 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_indegrees {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] : digraph_edge_count G = ∑ v, (Finset.univ.filter fun u => G.Adj u v).card := by rw [digraph_edge_count_eq_sum_outdegrees] simp only [Finset.card_filter] exact Finset.sum_comm