flow_cut_divergence_eq
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.
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ᶜ.
uses
Finset.sum_add_sum_complhave 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
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ᶜ.
uses
Finset.sum_add_sum_complhave 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
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ᶜ.
uses
Finset.sum_congr,Finset.sum_ite_memhave 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))
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ᶜ.
uses
Finset.sum_congr,Finset.sum_ite_memhave 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))
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.
uses
Finset.sum_add_distrib,Finset.sum_congrhave 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
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.
uses
Finset.sum_add_distrib,Finset.sum_congrhave 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
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.
uses
Finset.sum_commhave hA : (∑ v ∈ S, ∑ w ∈ S, f v w) = (∑ v ∈ S, ∑ u ∈ S, f u v) := by rw [Finset.sum_comm]
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.
uses
Finset.sum_congrhave 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
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.
uses
Finset.sum_congrhave 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
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.
uses
Finset.sum_sub_distribrw [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.
- In the formal statement, the cut-crossing flows are written using an if-then-else indicator over the entire vertex type (for example, summing `if w ∈ S then 0 else f v w` over all vertices w) rather than directly as sums over the complement Sᶜ. The lemmas hcompl_out and hcompl_in bridge this gap.
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.
/-- 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