Why Cuts Bound Flow
A feasible flow sends material from a source \(s\) to a sink \(t\), respecting each arc's capacity and conserving flow at every other vertex. A cut separates the source from the sink. Any net flow from one side of that separation to the other must use arcs directed out of the source side, and their total capacity limits how much can cross. This gives a bound that applies to every feasible flow, regardless of how the flow was constructed.
Throughout, a network is a finite directed graph with distinct vertices \(s\) and \(t\), called the source and sink, and a finite nonnegative capacity \(c(e)\) on each arc \(e\). Oppositely directed arcs may both be present. A flow assigns a number \(f(e)\) to each arc, with \(0\le f(e)\le c(e)\). At every vertex other than \(s,t\), the total flow on outgoing arcs equals the total flow on incoming arcs. The flow value \(|f|\) is the net flow out of \(s\): outgoing flow minus incoming flow. The zero flow is feasible, so the set of feasible flows is nonempty.
For a set \(S\), write \(\delta^+(S)\) for the arcs directed from \(S\) to \(V\setminus S\), and \(\delta^-(S)\) for the arcs directed from \(V\setminus S\) into \(S\). Thus \(c(S,V\setminus S)=\sum_{e\in\delta^+(S)}c(e)\). The flow across a cut is a net quantity: flow out across \(\delta^+(S)\) minus flow in across \(\delta^-(S)\).
The Flow-Cut Identity
Proof. For each vertex \(v\), let its balance be the total flow on arcs leaving \(v\) minus the total flow on arcs entering \(v\). Sum these balances over all vertices in \(S\). Every arc with both endpoints in \(S\) contributes once positively at its tail and once negatively at its head, so these contributions cancel. The remaining terms are the flows on arcs leaving \(S\) minus the flows on arcs entering \(S\). On the other hand, every vertex in \(S\) other than \(s\) is not \(t\), so its balance is zero by conservation. The sum of balances over \(S\) is therefore just the balance at \(s\), which is \(|f|\). Equating the two expressions proves the identity. \(\square\)
The identity applies to every cut, not only one that separates the graph in a visually simple way. It also accounts for arcs entering \(S\): their flow subtracts from the net flow across the cut. Their capacities, however, will not be subtracted from the cut capacity.
Weak Duality for Flows and Cuts
Proof. By the flow-cut identity, $$ |f|=\sum_{e\in\delta^+(S)}f(e)-\sum_{e\in\delta^-(S)}f(e). $$ Each incoming flow \(f(e)\) is nonnegative, so subtracting the incoming-flow sum can only decrease the expression. For every outgoing arc, feasibility gives \(f(e)\le c(e)\). Therefore $$ |f|\le\sum_{e\in\delta^+(S)}f(e)\le\sum_{e\in\delta^+(S)}c(e)=c(S,V\setminus S). $$ This proves the inequality for the specified flow and cut, both of which were arbitrary. Since it holds for every feasible flow, it bounds the maximum feasible value as well. \(\square\)
There is a maximum feasible flow in this finite setting: the feasible flows form a nonempty closed subset of the finite product of intervals \([0,c(e)]\), and so form a compact set. The flow value is a continuous function of the arc flows, so it attains a maximum on that set. Thus the theorem bounds an attained maximum, not merely a supremum. It does not say that the bound is attained by some flow; a cut may give a strict upper bound.
Worked Example: A Cut Gives an Upper Bound
Consider the directed network with vertex set \(V=\{s,a,b,t\}\) and exactly these arcs, with capacities shown: \(s\to a\) has capacity \(4\), \(s\to b\) has capacity \(3\), \(a\to b\) has capacity \(2\), \(a\to t\) has capacity \(3\), and \(b\to t\) has capacity \(4\).
Define a flow by $$ f(s\to a)=3,\quad f(s\to b)=2,\quad f(a\to b)=1,\quad f(a\to t)=2,\quad f(b\to t)=3. $$ Each value is between zero and its capacity: \(3\le4\), \(2\le3\), \(1\le2\), \(2\le3\), and \(3\le4\). At \(a\), inflow is \(3\) and outflow is \(1+2=3\). At \(b\), inflow is \(2+1=3\) and outflow is \(3\). Thus conservation holds, and the flow value is \(3+2=5\).
Choose \(S=\{s,a\}\), which contains \(s\) but not \(t\). The outgoing cut arcs are \(s\to b\), \(a\to b\), and \(a\to t\), so the cut capacity is \(3+2+3=8\). Their total flow is \(2+1+2=5\), and there are no arcs entering \(S\). The flow-cut identity gives \(5=5-0\), while weak duality gives \(5\le8\). In particular, no feasible flow in this network can have value greater than \(8\).
Check: the chosen flow has value \(3+2=5\), while the cut capacity is \(3+2+3=8\), so the computed values satisfy \(5\le8\) as required.
Worked Example: Accounting for Flow Into the Cut
Take \(V=\{s,a,b,t\}\) and exactly the arcs \(s\to a\) (capacity \(5\)), \(s\to b\) (capacity \(3\)), \(b\to a\) (capacity \(10\)), \(a\to t\) (capacity \(6\)), and \(b\to t\) (capacity \(2\)). Set the flows to \(5,2,1,6,1\), respectively.
The capacity checks are \(5\le5\), \(2\le3\), \(1\le10\), \(6\le6\), and \(1\le2\). Vertex \(a\) receives \(5+1=6\) and sends \(6\). Vertex \(b\) receives \(2\) and sends \(1+1=2\). Both internal vertices conserve flow, and \(|f|=5+2=7\).
For \(S=\{s,a\}\), the outgoing cut arcs are \(s\to b\) and \(a\to t\). The incoming cut arc is \(b\to a\). The outgoing capacity is \(3+6=9\), so weak duality gives \(|f|\le9\). More precisely, the flow-cut identity calculates the value as outgoing flow minus incoming flow: $$ |f|=(2+6)-1=7. $$ The incoming flow reduces the net flow across the cut, but it does not change the cut capacity \(9\).
Check: the source sends \(5+2=7\) units and has no incoming arcs, so its net outflow is \(7\), matching the cut calculation \(2+6-1=7\).
Worked Example: Comparing All Cuts in a Small Network
Let \(V=\{s,a,b,t\}\), with exactly the arcs \(s\to a\) (capacity \(4\)), \(s\to b\) (capacity \(2\)), \(a\to b\) (capacity \(1\)), \(a\to t\) (capacity \(2\)), and \(b\to t\) (capacity \(4\)). Consider the flow $$ f(s\to a)=3,\quad f(s\to b)=1,\quad f(a\to b)=1,\quad f(a\to t)=2,\quad f(b\to t)=2. $$ All five capacity checks hold: \(3\le4\), \(1\le2\), \(1\le1\), \(2\le2\), and \(2\le4\). Vertex \(a\) receives \(3\) and sends \(1+2=3\); vertex \(b\) receives \(1+1=2\) and sends \(2\). The flow value is \(3+1=4\).
Every cut is determined by whether \(a\) and \(b\) belong to \(S\), so there are \(2^2=4\) cuts. Their capacities are:
| Cut side \(S\) | Outgoing cut arcs | Capacity |
|---|---|---|
| \(\{s\}\) | \(s\to a,\ s\to b\) | \(4+2=6\) |
| \(\{s,a\}\) | \(s\to b,\ a\to b,\ a\to t\) | \(2+1+2=5\) |
| \(\{s,b\}\) | \(s\to a,\ b\to t\) | \(4+4=8\) |
| \(\{s,a,b\}\) | \(a\to t,\ b\to t\) | \(2+4=6\) |
The smallest of these four capacities is \(5\), from \(S=\{s,a\}\). For any feasible flow, weak duality applied to that cut gives an upper bound of \(5\). For the displayed flow, the outgoing flow across that cut is \(1+1+2=4\), with no incoming cut arcs, so its value \(4\) is consistent with the bound. The minimum among a collection of cut capacities is also an upper bound, because each cut in the collection bounds every feasible flow.
Check: the listed cut capacities are \(6,5,8,6\), whose minimum is \(5\); the displayed flow value \(4\) satisfies \(4\le5\).
Using the Bound and Avoiding a Common Error
To certify an upper bound on the maximum flow, it is enough to specify one \(s\)-\(t\) cut and add the capacities of its outgoing arcs. The cut need not be minimum: a larger cut capacity is still a valid upper bound, though it may be less informative. If several cuts are available, the smallest capacity among them gives the strongest bound from that collection. Weak duality alone does not say that any particular cut bound is sharp.
Common mistake: subtracting incoming capacity. In the second example, the outgoing capacity of \(S=\{s,a\}\) is \(3+6=9\), and the incoming arc \(b\to a\) has capacity \(10\). A mistaken calculation might use \(9-10=-1\) as an upper bound. But the feasible flow already computed has value \(7\), so \(-1\) cannot be an upper bound. The correction is to distinguish the two calculations: the flow-cut identity subtracts the actual incoming flow, giving \(8-1=7\), whereas the cut capacity sums only outgoing capacities, giving \(9\). Since incoming flow is nonnegative, it can only make net flow smaller; incoming capacity is not a deduction from the outgoing capacity.
The direction of each arc matters. An arc from \(S\) to \(V\setminus S\) contributes to the cut capacity; an arc in the opposite direction does not. The proof works even when arcs cross the cut in both directions, because the identity accounts for the net flow while the capacity bound controls all outgoing flow.
Check Your Understanding
For each question, use the definitions and inequalities proved above.
- For a feasible flow and an \(s\)-\(t\) cut, explain why arcs with both endpoints in \(S\) cancel when vertex balances are summed over \(S\).
- A cut has outgoing capacity \(12\), outgoing flow \(9\), and incoming flow \(2\). What value does the flow-cut identity give, and what upper bound does weak duality give?
- Explain why the minimum capacity among any specified collection of \(s\)-\(t\) cuts is an upper bound on every feasible flow value.
- Can a cut have positive incoming flow and still have capacity zero? Give the condition on its outgoing arcs that would make this possible.
- In the second worked example, compute the cut capacity again using only the capacities of arcs directed from \(S\) to \(V\setminus S\). Why is the capacity of \(b\to a\) excluded?