AFTD Auto-Formalizing Theoretical Domains

flow_rate_mul_sep_le_cut_capacity

theoremverified

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.

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

    line 7

      obtain ⟨f, hnn, hcap, hdiv⟩ := h
  2. For 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.

    lines 8–24

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

    lines 25–32

    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
  4. 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`).

    lines 33–59

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

    lines 60–65

    uses cutSeparation_eq_sum, Finset.sum_congr

      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]
  6. 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).

    lines 66–71

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

    lines 72–82

    uses Finset.sum_add_distrib, Finset.sum_congr, if_false

      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]
  8. 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)).

    lines 83–91

    uses Finset.sum_comm, Finset.sum_congr, 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]
  9. 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.

    lines 92–101

    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))
  10. 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).

    lines 102–109

    uses Finset.sum_congr

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

    line 110

    uses le_trans

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

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

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