AFTD Auto-Formalizing Theoretical Domains

digraph_edge_count_eq_sum_indegrees

theoremverified

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

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.

  1. 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)\\}|$.

    line 4

    uses digraph_edge_count_eq_sum_outdegrees

      rw [digraph_edge_count_eq_sum_outdegrees]
  2. 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)$.

    line 5

    uses Finset.card_filter

      simp only [Finset.card_filter]
  3. 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.

    line 6

    uses Finset.sum_comm

      exact 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

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