AFTD Auto-Formalizing Theoretical Domains

digraph_cut_sub_cut_eq_sum_net_degree

theoremverified

For any vertex subset A in a finite digraph G, the directed cut count e(A, Aᶜ) minus e(Aᶜ, A) equals the sum over vertices v in A of the net degree d⁺(v) - d⁻(v).

Statement

theorem digraph_cut_sub_cut_eq_sum_net_degree
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : Digraph V) [DecidableRel G.Adj] (A : Finset V) :
    ((digraph_cut_count G A Aᶜ : ℤ) - (digraph_cut_count G Aᶜ A : ℤ)) =
      ∑ v ∈ A, (((Finset.univ.filter (G.Adj v)).card : ℤ) -
        ((Finset.univ.filter fun u => G.Adj u v).card : ℤ))
Source
arXiv:2610.21381 Section 5
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.

Read back from the Lean

For every finite type $V$ with decidable equality, every directed graph $G$ on $V$ with decidable adjacency relation G.Adj, and every finset $A \subseteq V$, the difference between the number of directed edges from $A$ to its complement $A^c$ and the number of directed edges from $A^c$ to $A$ (cast to $\mathbb{Z}$) is equal to the sum over all vertices $v \in A$ of the out-degree of $v$ minus the in-degree of $v$ (both cast to $\mathbb{Z}$), where out-degree is the number of $w \in V$ such that $G.\text{Adj}(v, w)$ and in-degree is the number of $u \in V$ such that $G.\text{Adj}(u, v)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof expresses both the cut counts and the net degrees as double sums of directed edge indicator functions. For each vertex in A, its out-degree and in-degree are partitioned into edges incident to A and edges incident to Aᶜ. When summed over all vertices in A, the internal edges within A appear identically in both the total out-degree and total in-degree terms (by swapping summation variables) and cancel out, leaving exactly the difference between the directed cut sizes e(A, Aᶜ) and e(Aᶜ, A).

  1. The cut counts and net vertex degrees are expressed as nested sums of edge indicator functions, with the degree sum partitioned into out-degrees minus in-degrees.

    Unfolding `digraph_cut_count` and applying `card_filter` converts the cut sizes and the in- and out-degrees from set cardinalities into sums of 0-1 edge indicator functions (`if G.Adj ... then 1 else 0`). Coercions to the integers are pushed inside the sums using `push_cast`. Rewriting with `Finset.sum_product` turns the sums over the Cartesian products A × Aᶜ and Aᶜ × A into iterated double sums. Finally, `Finset.sum_sub_distrib` distributes the outer sum over the difference of out-degree and in-degree on the right-hand side.

    lines 8–12

    uses digraph_cut_count, card_filter, Finset.sum_product, Finset.sum_sub_distrib

      open Finset in
      simp only [digraph_cut_count, card_filter]
      push_cast
      rw [Finset.sum_product, Finset.sum_product]
      simp only [Finset.sum_sub_distrib]
  2. For any vertex x, the total out-degree splits into edges directed into A plus edges directed into Aᶜ.

    By function extensionality (`ext x`), the sum of out-edge indicators over all vertices decomposes into the sum over A and the sum over Aᶜ using `Finset.sum_add_sum_compl`.

    lines 13–16

    uses Finset.sum_add_sum_compl

      have h1 : (fun x => ∑ x_1, if G.Adj x x_1 then (1 : ℤ) else 0) =
          fun x => (∑ y ∈ A, if G.Adj x y then 1 else 0) + (∑ y ∈ Aᶜ, if G.Adj x y then 1 else 0) := by
        ext x
        exact (Finset.sum_add_sum_compl A _).symm
  3. For any vertex x, the total in-degree splits into edges directed from A plus edges directed from Aᶜ.

    Similarly, by function extensionality (`ext x`), the sum of in-edge indicators over all vertices decomposes into the sum over A and the sum over Aᶜ using `Finset.sum_add_sum_compl`.

    lines 17–20

    uses Finset.sum_add_sum_compl

      have h2 : (fun x => ∑ x_1, if G.Adj x_1 x then (1 : ℤ) else 0) =
          fun x => (∑ y ∈ A, if G.Adj y x then 1 else 0) + (∑ y ∈ Aᶜ, if G.Adj y x then 1 else 0) := by
        ext x
        exact (Finset.sum_add_sum_compl A _).symm
  4. The sum of net degrees over A expands into four double sums: (out-edges inside A + out-edges to Aᶜ) - (in-edges inside A + in-edges from Aᶜ).

    Rewriting with the decompositions `h1` and `h2` substitutes the split degree formulas into the goal, and `Finset.sum_add_distrib` distributes the outer sum over the additions.

    lines 21–22

    uses Finset.sum_add_distrib

      rw [h1, h2]
      simp only [Finset.sum_add_distrib]
  5. Swapping summation indices equates the double sum of in-edges within A to the double sum of out-edges within A, and reindexes the in-edges from Aᶜ.

    By `Finset.sum_comm`, the order of summation can be reversed: summing in-edges over x ∈ A and y ∈ A gives the same total as summing out-edges over A × A (`h_comm1`), and the sum of in-edges over x ∈ A and y ∈ Aᶜ equals the cut sum with y ∈ Aᶜ on the outside and x ∈ A on the inside (`h_comm2`).

    lines 23–26

    uses Finset.sum_comm

      have h_comm1 : (∑ x ∈ A, ∑ y ∈ A, if G.Adj y x then (1 : ℤ) else 0) =
          ∑ x ∈ A, ∑ y ∈ A, if G.Adj x y then (1 : ℤ) else 0 := Finset.sum_comm
      have h_comm2 : (∑ x ∈ A, ∑ y ∈ Aᶜ, if G.Adj y x then (1 : ℤ) else 0) =
          ∑ y ∈ Aᶜ, ∑ x ∈ A, if G.Adj y x then (1 : ℤ) else 0 := Finset.sum_comm
  6. The cut difference e(A, Aᶜ) - e(Aᶜ, A) equals the sum of net degrees over A.

    Rewriting with `h_comm1` and `h_comm2` aligns the internal edge sums so that the edges within A appear identically in both the positive and negative parts. The `ring` tactic cancels these internal edges, simplifying (T_internal + e(A, Aᶜ)) - (T_internal + e(Aᶜ, A)) to e(A, Aᶜ) - e(Aᶜ, A).

    lines 27–28

      rw [h_comm1, h_comm2]
      ring
digraph_cut_count
the number of directed edges from vertex set A to vertex set B, defined as the cardinality of pairs (u, v) ∈ A × B with an edge from u to v
card_filter
the cardinality of a filtered set {i ∈ s | p i} equals the sum over i ∈ s of the indicator function (1 if p i else 0)
Finset.sum_product
a sum over a Cartesian product s ×ˢ t equals the iterated sum over x ∈ s and y ∈ t
Finset.sum_sub_distrib
the sum of a difference of functions equals the difference of the sums of the functions
Finset.sum_add_sum_compl
the sum of a function over a subset s plus the sum over its complement sᶜ equals the sum over the entire domain
Finset.sum_add_distrib
the sum of a sum of functions equals the sum of each function summed separately
Finset.sum_comm
the order of summation in an iterated finite sum can be interchanged

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

/-- The difference between directed cut sizes in opposite directions across a vertex subset equals the sum of net degrees over the subset. -/theorem digraph_cut_sub_cut_eq_sum_net_degree    {V : Type*} [Fintype V] [DecidableEq V]    (G : Digraph V) [DecidableRel G.Adj] (A : Finset V) :    ((digraph_cut_count G A Aᶜ : ℤ) - (digraph_cut_count G Aᶜ A : ℤ)) =      ∑ v ∈ A, (((Finset.univ.filter (G.Adj v)).card : ℤ) -        ((Finset.univ.filter fun u => G.Adj u v).card : ℤ)) := by  open Finset in  simp only [digraph_cut_count, card_filter]  push_cast  rw [Finset.sum_product, Finset.sum_product]  simp only [Finset.sum_sub_distrib]  have h1 : (fun x => ∑ x_1, if G.Adj x x_1 then (1 : ℤ) else 0) =      fun x => (∑ y ∈ A, if G.Adj x y then 1 else 0) + (∑ y ∈ Aᶜ, if G.Adj x y then 1 else 0) := by    ext x    exact (Finset.sum_add_sum_compl A _).symm  have h2 : (fun x => ∑ x_1, if G.Adj x_1 x then (1 : ℤ) else 0) =      fun x => (∑ y ∈ A, if G.Adj y x then 1 else 0) + (∑ y ∈ Aᶜ, if G.Adj y x then 1 else 0) := by    ext x    exact (Finset.sum_add_sum_compl A _).symm  rw [h1, h2]  simp only [Finset.sum_add_distrib]  have h_comm1 : (∑ x ∈ A, ∑ y ∈ A, if G.Adj y x then (1 : ℤ) else 0) =      ∑ x ∈ A, ∑ y ∈ A, if G.Adj x y then (1 : ℤ) else 0 := Finset.sum_comm  have h_comm2 : (∑ x ∈ A, ∑ y ∈ Aᶜ, if G.Adj y x then (1 : ℤ) else 0) =      ∑ y ∈ Aᶜ, ∑ x ∈ A, if G.Adj y x then (1 : ℤ) else 0 := Finset.sum_comm  rw [h_comm1, h_comm2]  ring
See it in the graphDiscuss this resultChallenge it