Recipe

Compute an s-t cut's capacity

Use when: you're given a partition of the vertices into S and T (with s in S and t in T) and need its capacity, or need to check whether a flow is already maximum

Goal: the cut's exact capacity, plus enough evidence to say whether a given flow is provably maximum

Taught in The max-flow min-cut theorem · extends Build the residual graph and find an augmenting path

1. 1

   Find every edge with one endpoint in S and the other in T, in either direction. These are the only candidates.

   Example

   On S=\{s,b\}, T=\{a,t\} with edges s\to a (3), s\to b (3), a\to b (1), a\to t (3), b\to t (3): s\to b and a\to t stay on one side each, so only s\to a (3), a\to b (1), and b\to t (3) touch the boundary.

   Why: an edge with both endpoints on the same side can never separate s from t, so it can be ignored immediately.

2. 2

   Check each boundary edge's direction against the partition, one at a time. Direction is everything here.

   Example

   s\to a runs S\to T: keep it. b\to t runs S\to T: keep it. a\to b runs from a\in T to b\in S: that's T\to S.

   • the edge runs from S to T — keep it, its capacity counts toward the sum.
   • the edge runs from T to S — discard it; it contributes zero, no matter how large its capacity is.

   ⚡ Shortcut

   If S=\{s\} alone, skip the direction check: every edge leaving s is automatically S\to T, since every other vertex sits in T. On s\to a (4), s\to b (3) with S=\{s\}, both edges leave s, so both count.

   Why: severing every S\to T edge already disconnects s from t completely; a T\to S edge could never have carried anything toward t in the first place.

3. 3

   Add up the capacities of only the edges that survived the direction check. That total is \operatorname{cap}(S,T).

   Example

   Keeping s\to a (3) and b\to t (3) and dropping a\to b: \operatorname{cap}(\{s,b\},\{a,t\}) = 3+3 = 6.

   Why: capacity is defined as exactly this sum, nothing more and nothing less.

4. 4

   Weak duality guarantees a flow's value never exceeds any cut's capacity, so use that to read the comparison.

   Example

   The network above has a maximum flow of value 6. Since 6 \leq 6 and the two numbers actually match, neither can improve.

   • the flow's value is strictly less than the cut's capacity — neither is proven optimal yet; look for a larger flow or a tighter cut.
   • the flow's value equals the cut's capacity exactly — both are certified optimal, by weak duality alone.

   Why: a flow that reaches some cut's capacity can never be beaten, since no flow can ever exceed any cut.