AFTD Auto-Formalizing Theoretical Domains

digraph_edge_count_eq_cut_add

theoremverified

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

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.

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

    line 5

    uses Finset.card_filter

      simp only [digraph_edge_count, digraph_cut_count, Finset.card_filter]
  2. 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, ....

    lines 6–7

    uses Finset.univ_product_univ, Finset.sum_product

      rw [← Finset.univ_product_univ, Finset.sum_product, Finset.sum_product, Finset.sum_product,
        Finset.sum_product, Finset.sum_product]
  3. 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ᶜ.

    line 8

    uses Finset.sum_add_sum_compl

      rw [← Finset.sum_add_sum_compl A]
  4. 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ᶜ.

    line 9

    uses Finset.sum_add_sum_compl, Finset.sum_add_distrib

      simp only [← Finset.sum_add_sum_compl A, Finset.sum_add_distrib]
  5. 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.

    line 10

      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.

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