AFTD Auto-Formalizing Theoretical Domains

flow_cut_divergence_eq

theoremverified

Summing net vertex divergence of any flow f over a vertex set S equals the cut-crossing flow leaving S minus the cut-crossing flow entering S.

Statement

theorem flow_cut_divergence_eq
    {V : Type} [Fintype V] [DecidableEq V]
    (f : V → V → ℝ) (S : Finset V) :
    ∑ v ∈ S, ((∑ w, f v w) - (∑ u, f u v)) =
    (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f v w)) - (∑ v ∈ S, ∑ u, (if u ∈ S then 0 else f u v))
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • flow_rate_mul_sep_le_cut_capacityIf a fractional multicommodity flow supports the common rate r, then for every vertex set S, r times the number of sessions crossing S is…

The proof, explained

The net vertex divergence summed over S is expanded by splitting both the outgoing and incoming flow at each vertex v ∈ S into contributions from S and from the complement Sᶜ. The internal flow terms on S × S appear with opposite signs in the outgoing and incoming sums, and exchanging the summation order via Fubini's theorem shows they are identical and cancel out. The remaining terms are precisely the cut-crossing flow leaving S minus the cut-crossing flow entering S.

  1. For any vertex v, the total outgoing flow from v decomposes into the sum of flows to vertices in S and flows to vertices in Sᶜ.

    By applying `Finset.sum_add_sum_compl`, the sum over all vertices in V is split into the sum over S and the sum over its complement Sᶜ.

    lines 7–9

    uses Finset.sum_add_sum_compl

      have hsplit_out (v : V) :
          (∑ w, f v w) = (∑ w ∈ S, f v w) + (∑ w ∈ Sᶜ, f v w) := by
        exact (Finset.sum_add_sum_compl S (fun w => f v w)).symm
  2. For any vertex v, the total incoming flow into v decomposes into the sum of flows from vertices in S and flows from vertices in Sᶜ.

    Similarly, `Finset.sum_add_sum_compl` splits the sum over all vertices in V into the sum over S and the sum over its complement Sᶜ.

    lines 10–12

    uses Finset.sum_add_sum_compl

      have hsplit_in (v : V) :
          (∑ u, f u v) = (∑ u ∈ S, f u v) + (∑ u ∈ Sᶜ, f u v) := by
        exact (Finset.sum_add_sum_compl S (fun u => f u v)).symm
  3. For any vertex v, summing the conditional expression (if w ∈ S then 0 else f v w) over all vertices w equals the sum of f v w over w ∈ Sᶜ.

    First, a case split on whether w ∈ S shows that the summand is pointwise equal to (if w ∈ Sᶜ then f v w else 0). Then, `Finset.sum_ite_mem` simplifies the sum over all vertices to the sum over the complement Sᶜ.

    lines 13–24

    uses Finset.sum_congr, Finset.sum_ite_mem

      have hcompl_out (v : V) :
          (∑ w, (if w ∈ S then 0 else f v w)) = ∑ w ∈ Sᶜ, f v w := by
        calc
          (∑ w, (if w ∈ S then 0 else f v w))
              = ∑ w, (if w ∈ Sᶜ then f v w else 0) := by
                apply Finset.sum_congr rfl
                intro w _
                by_cases hw : w ∈ S
                · simp [hw]
                · simp [hw]
          _ = ∑ w ∈ Sᶜ, f v w := by
                simpa using (Finset.sum_ite_mem (Finset.univ : Finset V) Sᶜ (fun w => f v w))
  4. For any vertex v, summing the conditional expression (if u ∈ S then 0 else f u v) over all vertices u equals the sum of f u v over u ∈ Sᶜ.

    By the same case split on whether u ∈ S, the summand is pointwise equal to (if u ∈ Sᶜ then f u v else 0), and `Finset.sum_ite_mem` simplifies the sum over all vertices to the sum over Sᶜ.

    lines 25–36

    uses Finset.sum_congr, Finset.sum_ite_mem

      have hcompl_in (v : V) :
          (∑ u, (if u ∈ S then 0 else f u v)) = ∑ u ∈ Sᶜ, f u v := by
        calc
          (∑ u, (if u ∈ S then 0 else f u v))
              = ∑ u, (if u ∈ Sᶜ then f u v else 0) := by
                apply Finset.sum_congr rfl
                intro u _
                by_cases hu : u ∈ S
                · simp [hu]
                · simp [hu]
          _ = ∑ u ∈ Sᶜ, f u v := by
                simpa using (Finset.sum_ite_mem (Finset.univ : Finset V) Sᶜ (fun u => f u v))
  5. Summing the total outgoing flow over all v ∈ S decomposes into the internal flow within S plus the cut-crossing flow leaving S to Sᶜ.

    Using `Finset.sum_add_distrib` in reverse and sum congruence (`Finset.sum_congr`), each inner sum splits into the sum over S and the sum over Sᶜ via the decomposition hsplit_out.

    lines 37–42

    uses Finset.sum_add_distrib, Finset.sum_congr

      have hL1 : (∑ v ∈ S, ∑ w, f v w) =
          (∑ v ∈ S, ∑ w ∈ S, f v w) + (∑ v ∈ S, ∑ w ∈ Sᶜ, f v w) := by
        rw [← Finset.sum_add_distrib]
        apply Finset.sum_congr rfl
        intro v _
        exact hsplit_out v
  6. Summing the total incoming flow over all v ∈ S decomposes into the internal flow within S plus the cut-crossing flow entering S from Sᶜ.

    Similarly, using `Finset.sum_add_distrib` in reverse and sum congruence (`Finset.sum_congr`), each inner sum splits into the sum over S and the sum over Sᶜ via the decomposition hsplit_in.

    lines 43–48

    uses Finset.sum_add_distrib, Finset.sum_congr

      have hL2 : (∑ v ∈ S, ∑ u, f u v) =
          (∑ v ∈ S, ∑ u ∈ S, f u v) + (∑ v ∈ S, ∑ u ∈ Sᶜ, f u v) := by
        rw [← Finset.sum_add_distrib]
        apply Finset.sum_congr rfl
        intro v _
        exact hsplit_in v
  7. The total internal flow leaving vertices in S to vertices in S equals the total internal flow entering vertices in S from vertices in S.

    Interchanging the two summations over S using `Finset.sum_comm` shows that ∑ v ∈ S, ∑ w ∈ S, f v w equals ∑ v ∈ S, ∑ u ∈ S, f u v.

    lines 49–50

    uses Finset.sum_comm

      have hA : (∑ v ∈ S, ∑ w ∈ S, f v w) = (∑ v ∈ S, ∑ u ∈ S, f u v) := by
        rw [Finset.sum_comm]
  8. The first term on the right-hand side, representing the flow leaving S, equals the sum over v ∈ S and w ∈ Sᶜ of f v w.

    By sum congruence (`Finset.sum_congr`), each inner sum is replaced pointwise by the simplified sum over Sᶜ from hcompl_out.

    lines 51–55

    uses Finset.sum_congr

      have hR1 : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f v w)) =
          ∑ v ∈ S, ∑ w ∈ Sᶜ, f v w := by
        apply Finset.sum_congr rfl
        intro v _
        exact hcompl_out v
  9. The second term on the right-hand side, representing the flow entering S, equals the sum over v ∈ S and u ∈ Sᶜ of f u v.

    Similarly, sum congruence (`Finset.sum_congr`) replaces each inner sum pointwise with the sum over Sᶜ from hcompl_in.

    lines 56–60

    uses Finset.sum_congr

      have hR2 : (∑ v ∈ S, ∑ u, (if u ∈ S then 0 else f u v)) =
          ∑ v ∈ S, ∑ u ∈ Sᶜ, f u v := by
        apply Finset.sum_congr rfl
        intro v _
        exact hcompl_in v
  10. The sum of net vertex divergences over S equals the cut-crossing flow leaving S minus the cut-crossing flow entering S.

    We distribute the summation over subtraction on the left-hand side with `Finset.sum_sub_distrib` and substitute the decompositions hL1 and hL2. The internal flow terms cancel because they are equal by hA. Substituting the simplified cut expressions hR1 and hR2 into the right-hand side leaves an identity of the form (A + B) - (A + C) = B - C, which `ring` simplifies to complete the proof.

    lines 61–62

    uses Finset.sum_sub_distrib

      rw [hR1, hR2, Finset.sum_sub_distrib, hL1, hL2, hA]
      ring
Finset.sum_add_sum_compl
For a finite set s, summing a function over s plus summing it over the complement sᶜ equals the sum over the entire type.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second function.
Finset.sum_comm
The order of summation in a double sum over two finite sets can be exchanged (Fubini's theorem for finite sums).
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.sum_ite_mem
Summing a conditional expression that evaluates to f(i) when i ∈ t and 0 otherwise over a set s equals the sum of f(i) over the intersection s ∩ t.
Finset.sum_sub_distrib
The sum of a pointwise difference of two functions over a finite set equals the sum of the first function minus the sum of the second function.

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

/-- Summing net vertex divergence of any flow f over a vertex set S equals the cut-crossing flow leaving S minus the cut-crossing flow entering S. -/theorem flow_cut_divergence_eq    {V : Type} [Fintype V] [DecidableEq V]    (f : V → V → ℝ) (S : Finset V) :    ∑ v ∈ S, ((∑ w, f v w) - (∑ u, f u v)) =    (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f v w)) - (∑ v ∈ S, ∑ u, (if u ∈ S then 0 else f u v)) := by  have hsplit_out (v : V) :      (∑ w, f v w) = (∑ w ∈ S, f v w) + (∑ w ∈ Sᶜ, f v w) := by    exact (Finset.sum_add_sum_compl S (fun w => f v w)).symm  have hsplit_in (v : V) :      (∑ u, f u v) = (∑ u ∈ S, f u v) + (∑ u ∈ Sᶜ, f u v) := by    exact (Finset.sum_add_sum_compl S (fun u => f u v)).symm  have hcompl_out (v : V) :      (∑ w, (if w ∈ S then 0 else f v w)) = ∑ w ∈ Sᶜ, f v w := by    calc      (∑ w, (if w ∈ S then 0 else f v w))          = ∑ w, (if w ∈ Sᶜ then f v w else 0) := by            apply Finset.sum_congr rfl            intro w _            by_cases hw : w ∈ S            · simp [hw]            · simp [hw]      _ = ∑ w ∈ Sᶜ, f v w := by            simpa using (Finset.sum_ite_mem (Finset.univ : Finset V) Sᶜ (fun w => f v w))  have hcompl_in (v : V) :      (∑ u, (if u ∈ S then 0 else f u v)) = ∑ u ∈ Sᶜ, f u v := by    calc      (∑ u, (if u ∈ S then 0 else f u v))          = ∑ u, (if u ∈ Sᶜ then f u v else 0) := by            apply Finset.sum_congr rfl            intro u _            by_cases hu : u ∈ S            · simp [hu]            · simp [hu]      _ = ∑ u ∈ Sᶜ, f u v := by            simpa using (Finset.sum_ite_mem (Finset.univ : Finset V) Sᶜ (fun u => f u v))  have hL1 : (∑ v ∈ S, ∑ w, f v w) =      (∑ v ∈ S, ∑ w ∈ S, f v w) + (∑ v ∈ S, ∑ w ∈ Sᶜ, f v w) := by    rw [← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro v _    exact hsplit_out v  have hL2 : (∑ v ∈ S, ∑ u, f u v) =      (∑ v ∈ S, ∑ u ∈ S, f u v) + (∑ v ∈ S, ∑ u ∈ Sᶜ, f u v) := by    rw [← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro v _    exact hsplit_in v  have hA : (∑ v ∈ S, ∑ w ∈ S, f v w) = (∑ v ∈ S, ∑ u ∈ S, f u v) := by    rw [Finset.sum_comm]  have hR1 : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f v w)) =      ∑ v ∈ S, ∑ w ∈ Sᶜ, f v w := by    apply Finset.sum_congr rfl    intro v _    exact hcompl_out v  have hR2 : (∑ v ∈ S, ∑ u, (if u ∈ S then 0 else f u v)) =      ∑ v ∈ S, ∑ u ∈ Sᶜ, f u v := by    apply Finset.sum_congr rfl    intro v _    exact hcompl_in v  rw [hR1, hR2, Finset.sum_sub_distrib, hL1, hL2, hA]  ring
See it in the graphDiscuss this resultChallenge it