AFTD Auto-Formalizing Theoretical Domains

digraph_edge_count_eq_sum_outdegrees

theoremverified

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
Used by 2

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.

  1. 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.

    lines 4–5

    uses Finset.card_filter, Finset.univ_product_univ, Finset.sum_product

      unfold digraph_edge_count
      rw [Finset.card_filter, ← Finset.univ_product_univ, Finset.sum_product]
  2. 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.

    line 6

    uses Finset.card_filter

      simp 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

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