flow_session_cut_demand_eq
Summing 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.
Statement
theorem flow_session_cut_demand_eq {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] (sess : UnicastSessions V K) (r : ℝ) (k : K) (S : Finset V) : ∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0) = 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
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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,…
- 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 theorem computes the net demand of a unicast session across a cut $S$, where the source contributes $r$ and the target contributes $-r$. Because the source and target of any session are distinct, the summand splits into the sum of two separate single-vertex indicator functions. Evaluating each sum over $S$ leaves a sum of two conditionals, which simplifies across the four membership cases for the source and target to the required cut demand formula.
The sum decomposes into two separate sums: one for the source vertex demand and one for the target vertex demand.
We establish the lemma `hsplit`. Rewriting in reverse with `Finset.sum_add_distrib` merges the two sums into one. By `Finset.sum_congr`, it suffices to check pointwise equality of the summands for each $v \in S$. We split into cases on whether $v = \text{sess.src } k$: if so, since the source and target are distinct (`sess.src_ne_tgt`), $v \neq \text{sess.tgt } k$, so both the original summand and the sum of indicators equal $r$; if $v \neq \text{sess.src } k$, the source indicator is zero and both sides reduce to $-r$ when $v = \text{sess.tgt } k$ and $0$ otherwise.
uses
Finset.sum_add_distrib,Finset.sum_congr,sess.src_ne_tgthave hsplit : (∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0)) = (∑ v ∈ S, (if v = sess.src k then r else 0)) + (∑ v ∈ S, (if v = sess.tgt k then -r else 0)) := by rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro v hv by_cases hvs : v = sess.src k · simp [hvs, sess.src_ne_tgt k] · simp [hvs]
The sum evaluates to $(\text{if } \text{sess.src } k \in S \text{ then } r \text{ else } 0) + (\text{if } \text{sess.tgt } k \in S \text{ then } -r \text{ else } 0)$.
Rewriting with `hsplit` replaces the original sum with the two separate indicator sums. Applying `Finset.sum_ite_eq'` to each sum evaluates the summation over $S$: an indicator concentrated at a single point equals the value ($r$ or $-r$) if that point belongs to $S$, and $0$ if it does not.
uses
Finset.sum_ite_eq'rw [hsplit, Finset.sum_ite_eq', Finset.sum_ite_eq']The evaluated sum equals the conditional session cut demand formula.
We split into cases based on whether $\text{sess.src } k \in S$ and whether $\text{sess.tgt } k \in S$. In all four cases, arithmetic and propositional simplification verify the equality: when both vertices are in $S$, $r + (-r) = 0$; when only the source is in $S$, the sum is $r$; when only the target is in $S$, the sum is $-r$; and when neither is in $S$, $0 + 0 = 0$.
by_cases hsrc : sess.src k ∈ S <;> by_cases htgt : sess.tgt k ∈ S <;> simp [hsrc, htgt]
Finset.sum_add_distrib- The sum over a finite set distributes over addition: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Finset.sum_congr- Two sums over equal finite sets are equal if their summands agree on every element of the set.
Finset.sum_ite_eq'- Summing an indicator function that is $b(x)$ when $x = a$ and $0$ otherwise over a finite set $s$ yields $b(a)$ if $a \in s$, and $0$ if $a \notin s$.
sess.src_ne_tgt- For any session $k$, its source vertex is distinct from its target vertex: $\text{sess.src } k \neq \text{sess.tgt } k$.
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 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. -/theorem flow_session_cut_demand_eq {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] (sess : UnicastSessions V K) (r : ℝ) (k : K) (S : Finset V) : ∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0) = 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 have hsplit : (∑ v ∈ S, (if v = sess.src k then r else if v = sess.tgt k then -r else 0)) = (∑ v ∈ S, (if v = sess.src k then r else 0)) + (∑ v ∈ S, (if v = sess.tgt k then -r else 0)) := by rw [← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro v hv by_cases hvs : v = sess.src k · simp [hvs, sess.src_ne_tgt k] · simp [hvs] rw [hsplit, Finset.sum_ite_eq', Finset.sum_ite_eq'] by_cases hsrc : sess.src k ∈ S <;> by_cases htgt : sess.tgt k ∈ S <;> simp [hsrc, htgt]