flow_rate_mul_sep_le_cut_capacity
If a fractional multicommodity flow supports the common rate r, then for every vertex set S, r times the number of sessions crossing S is at most the total capacity leaving S.
Statement
theorem flow_rate_mul_sep_le_cut_capacity {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r : ℝ} (h : FlowSupportsRate net sess r) (S : Finset V) : r * (cutSeparation sess S : ℝ) ≤ cutCapacity net S
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- cutSeparationThe number of sessions (out of the unicast session set sess) with exactly one endpoint in the vertex set S, i.e. the number of sessions…
- cutCapacityThe total capacity of the edges of the network leaving a vertex set S: the sum over u ∈ S and all v of cap({u,v}), with the terms where v…
- FlowSupportsRateA common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a…
- flow_cut_divergence_eqSumming net vertex divergence of any flow f over a vertex set S equals the cut-crossing flow leaving S minus the cut-crossing flow…
- flow_session_cut_demand_eqSumming the session demand indicators over a cut S yields r if src ∈ S and tgt ∉ S, -r if src ∉ S and tgt ∈ S, and 0 otherwise.
- cutSeparation_eq_sumExpress cutSeparation as a sum of real indicator functions over sessions k in K.
- UnicastSessionsA collection of unicast communication sessions indexed by a type K on an arbitrary vertex type V, consisting of a source map src : K → V,…
- CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
- IsMulticommodityFlowGiven a capacitated network on a finite vertex type V with decidable equality, and unicast sessions indexed by a finite type K with…
The proof, explained
The proof establishes the cut condition for multicommodity flows: a supported rate r cannot exceed the capacity of any cut S divided by the number of sessions crossing S. The argument sandwiches the total multicommodity flow across the cut between two bounds. From below, flow conservation dictates that each session crossing S contributes at least r to the total cut flow, so the total cut flow is at least r times the cut separation. From above, the capacity constraints on individual edges bound the total flow across the cut by the cut capacity.
There exists a multicommodity flow f supporting the demand rate r.
From the hypothesis that the network supports rate r, we obtain a flow f satisfying non-negativity (`hnn`), edge capacity constraints for each undirected edge (`hcap`), and flow conservation matching the session demands of rate r at every vertex (`hdiv`).
obtain ⟨f, hnn, hcap, hdiv⟩ := hFor every session k, both the outflow from S and the inflow into S across the cut are non-negative.
The cut outflow ∑_{v ∈ S} ∑_{w ∉ S} f_k(v, w) and cut inflow ∑_{v ∈ S} ∑_{w ∉ S} f_k(w, v) are sums of non-negative flow values f_k(u, v) ≥ 0, so both sums are non-negative.
uses
Finset.sum_nonneg,if_false-- Each session's outflow across the cut, and its inflow across the cut. have hout_nn : ∀ k : K, 0 ≤ ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w) := by intro k refine Finset.sum_nonneg (fun v _ => ?_) refine Finset.sum_nonneg (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] exact hnn k v w have hinn_nn : ∀ k : K, 0 ≤ ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v) := by intro k refine Finset.sum_nonneg (fun v _ => ?_) refine Finset.sum_nonneg (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] exact hnn k w v
For each session k, the net flow out of S equals r if the source is in S and the target is in Sᶜ, -r if the source is in Sᶜ and the target is in S, and 0 otherwise.
By `flow_cut_divergence_eq`, the net cut flow (outflow minus inflow) equals the sum over v ∈ S of the vertex divergences. Substituting the divergence conservation condition `hdiv` and evaluating the sum of session demands over S using `flow_session_cut_demand_eq` yields r, -r, or 0 according to which endpoints of session k lie in S.
uses
flow_cut_divergence_eq,Finset.sum_congr,flow_session_cut_demand_eq-- Net flow across the cut equals the demand of the session summed over the cut. have hdiv_cut : ∀ k : K, (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = (if sess.src k ∈ S ∧ sess.tgt k ∉ S then r else if sess.src k ∉ S ∧ sess.tgt k ∈ S then -r else 0) := by intro k rw [← flow_cut_divergence_eq (f k) S] rw [Finset.sum_congr rfl (fun v _ => hdiv k v)] exact flow_session_cut_demand_eq sess r k S
For each session k, the total undirected flow across the cut is at least r if session k crosses S, and at least 0 otherwise. automation
We perform a case analysis on whether the source and target of session k belong to S. If the session crosses the cut, the net cut flow is r or -r; since both directed flows are non-negative, their sum is at least the absolute value of their difference, which is r. If the session does not cross, the sum of two non-negative terms is at least 0. Each case is verified by linear arithmetic (`linarith`).
-- Per session: the total flow across the cut in both directions is at least `r` if the -- session crosses the cut, and at least `0` otherwise. have hkey : ∀ k : K, r * (if sess.src k ∈ S ∧ sess.tgt k ∉ S then (1:ℝ) else if sess.src k ∉ S ∧ sess.tgt k ∈ S then 1 else 0) ≤ (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) := by intro k have hD := hdiv_cut k have hn1 := hout_nn k have hn2 := hinn_nn k by_cases hs : sess.src k ∈ S <;> by_cases ht : sess.tgt k ∈ S · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = 0 := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = r := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = -r := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = 0 := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith
The cut separation of S equals the sum over all sessions k of the indicator that session k crosses S.
Using `cutSeparation_eq_sum`, the number of sessions separated by the cut S is expressed as the sum over all k of a boolean indicator taking value 1 if the session crosses and 0 otherwise.
uses
cutSeparation_eq_sum,Finset.sum_congrhave hsep_eq : (cutSeparation sess S : ℝ) = ∑ k : K, (if sess.src k ∈ S ∧ sess.tgt k ∉ S then (1:ℝ) else if sess.src k ∉ S ∧ sess.tgt k ∈ S then 1 else 0) := by rw [cutSeparation_eq_sum] refine Finset.sum_congr rfl (fun k _ => ?_) by_cases hs : sess.src k ∈ S <;> by_cases ht : sess.tgt k ∈ S <;> simp [hs, ht]
The scaled separation r * cutSeparation(sess, S) is bounded above by the sum over all sessions of their total flow across the cut.
Distributing r into the indicator sum for cut separation via `Finset.mul_sum` and applying the per-session lower bound `hkey` term by term via `Finset.sum_le_sum` gives r * cutSeparation(sess, S) ≤ ∑_k (outflow_k + inflow_k).
uses
Finset.mul_sum,Finset.sum_le_sum-- Lower bound: sum the per-session inequality over all sessions. have hsum_lower : r * (cutSeparation sess S : ℝ) ≤ ∑ k : K, ((∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v))) := by rw [hsep_eq, Finset.mul_sum] exact Finset.sum_le_sum (fun k _ => hkey k)
For each session k, the sum of outflow and inflow across the cut can be combined into a single sum of f_k(v, w) + f_k(w, v) over crossing pairs (v, w) ∈ S × Sᶜ.
Using `Finset.sum_add_distrib`, the separate sums for outflow and inflow are merged into a single double sum over v ∈ S and w ∉ S of f_k(v, w) + f_k(w, v).
uses
Finset.sum_add_distrib,Finset.sum_congr,if_falsehave hmerge : ∀ k : K, (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else (f k v w + f k w v)) := by intro k rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl (fun v _ => ?_) rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false]
The total flow across the cut can be written by swapping the sum over sessions with the sums over cut edges.
Applying `Finset.sum_comm` twice exchanges the outer summation over sessions k with the summations over vertices v ∈ S and w ∉ S, yielding ∑_{v ∈ S} ∑_{w ∉ S} ∑_k (f_k(v, w) + f_k(w, v)).
uses
Finset.sum_comm,Finset.sum_congr,if_falsehave hstep : (∑ k : K, ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else (f k v w + f k w v))) = ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else ∑ k : K, (f k v w + f k w v)) := by rw [Finset.sum_comm] refine Finset.sum_congr rfl (fun v _ => ?_) rw [Finset.sum_comm] refine Finset.sum_congr rfl (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false]
The total flow across all cut edges is bounded by the cut capacity.
For any v ∈ S and w ∉ S, the vertices are distinct (v ≠ w), so the capacity constraint `hcap` guarantees that the total bidirectional flow ∑_k (f_k(v, w) + f_k(w, v)) is at most net.cap s(v, w). Summing this inequality over all v ∈ S and w ∉ S via `Finset.sum_le_sum` gives the cut capacity.
uses
Finset.sum_le_sum,if_false-- Upper bound: the capacity constraint, summed over the ordered crossing pairs. have hbound : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else ∑ k : K, (f k v w + f k w v))) ≤ cutCapacity net S := by simp only [cutCapacity] refine Finset.sum_le_sum (fun v hv => ?_) refine Finset.sum_le_sum (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] exact hcap v w (fun hvw => hw (hvw ▸ hv))
The sum of all session cut flows is at most the cut capacity.
Combining the merged session flow expression (`hmerge`), the swapped order of summation (`hstep`), and the edge capacity bound (`hbound`), the total flow across the cut across all sessions is at most cutCapacity(net, S).
uses
Finset.sum_congrhave hsum_upper : (∑ k : K, ((∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)))) ≤ cutCapacity net S := by have h1 : (∑ k : K, ((∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)))) = ∑ k : K, ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else (f k v w + f k w v)) := Finset.sum_congr rfl (fun k _ => hmerge k) rw [h1, hstep] exact hbound
r * cutSeparation(sess, S) ≤ cutCapacity(net, S).
By transitivity of inequality (`le_trans`), combining the lower bound r * cutSeparation ≤ (total cut flow) and the upper bound (total cut flow) ≤ cutCapacity completes the proof.
uses
le_transexact le_trans hsum_lower hsum_upper
Finset.sum_add_distrib- The sum of a pointwise sum over a finite set equals the sum of the sums: ∑ x, (f x + g x) = (∑ x, f x) + (∑ x, g x).
Finset.sum_comm- The order of summation in a double finite sum can be exchanged: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
Finset.sum_congr- Two finite sums over the same set are equal if their summands agree on every element: if s₁ = s₂ and f x = g x for all x ∈ s₂, then ∑ x ∈ s₁, f x = ∑ x ∈ s₂, g x.
Finset.sum_le_sum- If f x ≤ g x for all x in a finite set, then ∑ x, f x ≤ ∑ x, g x.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative: if 0 ≤ f x for all x ∈ s, then 0 ≤ ∑ x ∈ s, f x.
Finset.mul_sum- Multiplication distributes over a finite sum from the left: a * ∑ x, f x = ∑ x, a * f x.
cutSeparation_eq_sum- The cut separation of S equals the sum over all sessions of the indicator that the session crosses S: (cutSeparation sess S : ℝ) = ∑ k, if (src k ∈ S) ≠ (tgt k ∈ S) then 1 else 0.
flow_cut_divergence_eq- For any flow f and vertex set S, the sum of vertex divergences in S equals the cut outflow minus the cut inflow: ∑ v ∈ S, ((∑ w, f v w) - (∑ u, f u v)) = (∑ v ∈ S, ∑ w ∉ S, f v w) - (∑ v ∈ S, ∑ u ∉ S, f u v).
flow_session_cut_demand_eq- Summing session k's demand over S yields r if only the source is in S, -r if only the target is in S, and 0 otherwise.
if_false- An if-then-else whose condition is false simplifies to its else-branch: (if False then t else e) = e.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
- In the formalization, the complement of the vertex set S is represented by a conditional `if w ∈ S then 0 else ...` inside sums over all vertices.
- In the per-session lower bound (`hkey`, lines 35–59), after splitting into four cases based on whether the source and target belong to S, the resulting inequalities are closed by `linarith`.
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.
/-- A flow-supported rate is bounded on every cut by capacity over number of crossing sessions. -/theorem flow_rate_mul_sep_le_cut_capacity {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K] (net : CapacitatedNetwork V) (sess : UnicastSessions V K) {r : ℝ} (h : FlowSupportsRate net sess r) (S : Finset V) : r * (cutSeparation sess S : ℝ) ≤ cutCapacity net S := by obtain ⟨f, hnn, hcap, hdiv⟩ := h -- Each session's outflow across the cut, and its inflow across the cut. have hout_nn : ∀ k : K, 0 ≤ ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w) := by intro k refine Finset.sum_nonneg (fun v _ => ?_) refine Finset.sum_nonneg (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] exact hnn k v w have hinn_nn : ∀ k : K, 0 ≤ ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v) := by intro k refine Finset.sum_nonneg (fun v _ => ?_) refine Finset.sum_nonneg (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] exact hnn k w v -- Net flow across the cut equals the demand of the session summed over the cut. have hdiv_cut : ∀ k : K, (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = (if sess.src k ∈ S ∧ sess.tgt k ∉ S then r else if sess.src k ∉ S ∧ sess.tgt k ∈ S then -r else 0) := by intro k rw [← flow_cut_divergence_eq (f k) S] rw [Finset.sum_congr rfl (fun v _ => hdiv k v)] exact flow_session_cut_demand_eq sess r k S -- Per session: the total flow across the cut in both directions is at least `r` if the -- session crosses the cut, and at least `0` otherwise. have hkey : ∀ k : K, r * (if sess.src k ∈ S ∧ sess.tgt k ∉ S then (1:ℝ) else if sess.src k ∉ S ∧ sess.tgt k ∈ S then 1 else 0) ≤ (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) := by intro k have hD := hdiv_cut k have hn1 := hout_nn k have hn2 := hinn_nn k by_cases hs : sess.src k ∈ S <;> by_cases ht : sess.tgt k ∈ S · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = 0 := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = r := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = -r := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith · have hD' : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) - (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = 0 := by rw [hD]; simp [hs, ht] simp [hs, ht] linarith have hsep_eq : (cutSeparation sess S : ℝ) = ∑ k : K, (if sess.src k ∈ S ∧ sess.tgt k ∉ S then (1:ℝ) else if sess.src k ∉ S ∧ sess.tgt k ∈ S then 1 else 0) := by rw [cutSeparation_eq_sum] refine Finset.sum_congr rfl (fun k _ => ?_) by_cases hs : sess.src k ∈ S <;> by_cases ht : sess.tgt k ∈ S <;> simp [hs, ht] -- Lower bound: sum the per-session inequality over all sessions. have hsum_lower : r * (cutSeparation sess S : ℝ) ≤ ∑ k : K, ((∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v))) := by rw [hsep_eq, Finset.mul_sum] exact Finset.sum_le_sum (fun k _ => hkey k) have hmerge : ∀ k : K, (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)) = ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else (f k v w + f k w v)) := by intro k rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl (fun v _ => ?_) rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] have hstep : (∑ k : K, ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else (f k v w + f k w v))) = ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else ∑ k : K, (f k v w + f k w v)) := by rw [Finset.sum_comm] refine Finset.sum_congr rfl (fun v _ => ?_) rw [Finset.sum_comm] refine Finset.sum_congr rfl (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] -- Upper bound: the capacity constraint, summed over the ordered crossing pairs. have hbound : (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else ∑ k : K, (f k v w + f k w v))) ≤ cutCapacity net S := by simp only [cutCapacity] refine Finset.sum_le_sum (fun v hv => ?_) refine Finset.sum_le_sum (fun w _ => ?_) by_cases hw : w ∈ S · simp [hw] · simp only [hw, if_false] exact hcap v w (fun hvw => hw (hvw ▸ hv)) have hsum_upper : (∑ k : K, ((∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)))) ≤ cutCapacity net S := by have h1 : (∑ k : K, ((∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k v w)) + (∑ v ∈ S, ∑ w, (if w ∈ S then 0 else f k w v)))) = ∑ k : K, ∑ v ∈ S, ∑ w, (if w ∈ S then 0 else (f k v w + f k w v)) := Finset.sum_congr rfl (fun k _ => hmerge k) rw [h1, hstep] exact hbound exact le_trans hsum_lower hsum_upper