digraph_edge_count_eq_cut_add
For any vertex set A, the edges of a digraph split into those inside A, from A to its complement, from the complement to A, and inside the complement.
Statement
theorem digraph_edge_count_eq_cut_add {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A : Finset V) : digraph_edge_count G = digraph_cut_count G A A + digraph_cut_count G A Aᶜ + digraph_cut_count G Aᶜ A + digraph_cut_count G Aᶜ Aᶜ
- Source
- Sanity lemma for directed cuts, arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 1.
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
The proof, explained
The proof expresses the total edge count and the four cut counts as sums of edge indicators over pairs of vertices. It then rewrites the Cartesian product sums as nested double sums, and partitions the summation over all vertices V into sums over A and its complement Aᶜ for both coordinates. Distributing these sums yields the same four terms on both sides, which are seen to be equal by associativity and commutativity of addition.
The total edge count and all four cut counts are rewritten as sums of indicator values (1 if an edge exists, 0 otherwise) over their respective sets of vertex pairs.
Unfolding the definitions of digraph_edge_count and digraph_cut_count expresses each count as the cardinality of the pairs satisfying the adjacency condition. Applying Finset.card_filter converts each cardinality into the sum of the indicator function (if G.Adj u v then 1 else 0) over the corresponding set of pairs.
uses
Finset.card_filtersimp only [digraph_edge_count, digraph_cut_count, Finset.card_filter]All five sums over pairs are converted into iterated double sums over individual vertices.
The universal set of pairs is rewritten as the Cartesian product univ ×ˢ univ using Finset.univ_product_univ. Then, Finset.sum_product rewrites each sum over a Cartesian product into an iterated double sum ∑ x, ∑ y, ....
uses
Finset.univ_product_univ,Finset.sum_productrw [← Finset.univ_product_univ, Finset.sum_product, Finset.sum_product, Finset.sum_product, Finset.sum_product, Finset.sum_product]The outer sum over all vertices on the left-hand side splits into a sum over A and a sum over Aᶜ.
Using Finset.sum_add_sum_compl, the outer sum ∑ x over all vertices V is partitioned into the sum over x ∈ A plus the sum over x ∈ Aᶜ.
uses
Finset.sum_add_sum_complrw [← Finset.sum_add_sum_compl A]The inner sums over all vertices on the left-hand side split into sums over A and Aᶜ, expanding the left-hand side into four double sums.
Applying Finset.sum_add_sum_compl again splits the inner sum over all y into y ∈ A and y ∈ Aᶜ for each outer sum. Distributing the outer additions using Finset.sum_add_distrib expands the left-hand side into the four double sums over A × A, A × Aᶜ, Aᶜ × A, and Aᶜ × Aᶜ.
uses
Finset.sum_add_sum_compl,Finset.sum_add_distribsimp only [← Finset.sum_add_sum_compl A, Finset.sum_add_distrib]The total edge count equals the sum of the four cut counts.
Both sides now consist of the exact same four double sums, grouped only with different parenthesisation. The equality is closed by the associativity and commutativity of addition.
ring
Finset.card_filter- The cardinality of a filtered subset {x ∈ s | p x} equals the sum over s of the indicator function (1 if p x holds, and 0 otherwise).
Finset.univ_product_univ- The Cartesian product of the universal sets of two finite types is the universal set of the product type.
Finset.sum_product- A sum over a Cartesian product s ×ˢ t of pairs equals the iterated double sum over s and t.
Finset.sum_add_sum_compl- The sum of a function over a finite type equals the sum over a subset s plus the sum over its complement sᶜ.
Finset.sum_add_distrib- A sum of a pointwise sum of two functions equals the sum of the first plus the sum of the second.
- On paper, this result is typically proved by noting that the Cartesian product V × V partitions into the four disjoint sets A × A, A × Aᶜ, Aᶜ × A, and Aᶜ × Aᶜ, so the edges partition accordingly. The Lean proof instead formalises this via indicator functions and summation lemmas.
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_cut_add {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A : Finset V) : digraph_edge_count G = digraph_cut_count G A A + digraph_cut_count G A Aᶜ + digraph_cut_count G Aᶜ A + digraph_cut_count G Aᶜ Aᶜ := by simp only [digraph_edge_count, digraph_cut_count, Finset.card_filter] rw [← Finset.univ_product_univ, Finset.sum_product, Finset.sum_product, Finset.sum_product, Finset.sum_product, Finset.sum_product] rw [← Finset.sum_add_sum_compl A] simp only [← Finset.sum_add_sum_compl A, Finset.sum_add_distrib] ring