From a Flow Bound to an Equality
A flow sends material from a source \(s\) to a distinct sink \(t\), subject to capacities on directed arcs and conservation at every other vertex. A cut separates \(s\) from \(t\), and its capacity is the total capacity of arcs directed from the source side to the sink side. The key contrast is that a flow can use only what the network permits, while a cut gives a limit that no flow can exceed. The max-flow min-cut theorem says these two bounds meet exactly.
Throughout, a network is a finite directed graph with distinct vertices \(s,t\) and a nonnegative finite capacity \(c(e)\) on each arc \(e\). Oppositely directed arcs, if present, are treated as separate arcs. A feasible flow \(f\) assigns a number \(f(e)\) to each arc, with \(0\le f(e)\le c(e)\), and satisfies conservation at every vertex other than \(s,t\): total flow entering equals total flow leaving. Its value \(|f|\) is the net flow leaving \(s\). The zero flow is feasible, so the set of feasible flow values is nonempty.
The residual network records how a current flow can be changed. For an original arc \(e=u v\), its forward residual capacity is \(c(e)-f(e)\), and its reverse residual capacity, on the residual arc from \(v\) to \(u\), is \(f(e)\). A reverse residual arc represents the option to cancel some of the flow on \(e\); it is not an extra original arc. When opposite original arcs exist, residual arcs retain their association with the original arc that produced them.
Why Every Cut Bounds Every Flow
For a vertex set \(S\), sum the net outflow (outflow minus inflow) over all vertices in \(S\). Flows on arcs internal to \(S\) cancel: each such arc contributes once as outflow and once as inflow. If \(S\) contains \(s\) but not \(t\), conservation makes the sum equal to \(|f|\). Only arcs crossing the cut remain, giving the flow-cut identity.
Each flow amount is nonnegative, and \(f(e)\le c(e)\). Dropping the nonnegative incoming-flow sum and bounding each outgoing flow by its capacity gives the weak duality inequality.
Thus every feasible flow is bounded by every \(s\)-\(t\) cut. Weak duality alone does not show that any flow attains the smallest cut capacity. The residual network supplies the missing direction.
The Max-Flow Min-Cut Theorem
Proof. First, a maximum-value feasible flow exists. The zero flow is feasible. The set of all feasible assignments lies in the finite product of closed intervals \(\prod_e[0,c(e)]\), and the conservation equations define a closed subset of that product. It is therefore compact. The flow value is a continuous function of the arc assignments, so it attains a maximum on this nonempty compact set.
Let \(f\) be a maximum flow. There cannot be a residual path from \(s\) to \(t\). If one existed, choose a path with no repeated vertices and let \(\varepsilon\) be the smallest residual capacity of its arcs. The path has finitely many arcs, each with positive residual capacity, so \(\varepsilon>0\). Increase the original flow by \(\varepsilon\) on each forward residual arc of the path and decrease it by \(\varepsilon\) on each reverse residual arc. The residual-capacity bounds ensure that every changed flow remains between zero and its capacity. At each internal path vertex, the change in inflow equals the change in outflow, so conservation remains true. The source sends an additional \(\varepsilon\), contradicting maximality of \(f\).
Let \(S\) be the set of vertices reachable from \(s\) along residual arcs of positive capacity. Since there is no residual \(s\)-\(t\) path, \(t\notin S\), so \((S,\overline{S})\) is an \(s\)-\(t\) cut. Consider an original arc directed from \(S\) to \(\overline{S}\). If it were not saturated, its forward residual capacity \(c(e)-f(e)\) would be positive, making its endpoint reachable from \(s\). Thus every such arc has \(f(e)=c(e)\). Now consider an original arc directed from \(\overline{S}\) to \(S\). If it carried positive flow, its reverse residual arc would have positive capacity and would lead from \(S\) to \(\overline{S}\), again making its endpoint reachable. Thus every such arc has \(f(e)=0\). The flow-cut identity therefore gives \(|f|=c(S,\overline{S})\).
Weak duality says that no flow has value greater than any cut capacity. The cut just constructed has capacity equal to the value of a maximum flow. Consequently that flow is maximum, that cut is minimum, and their values are equal. \(\square\)
The argument also covers networks with zero-capacity arcs or no route from \(s\) to \(t\). In the latter case the zero flow is maximum, and the residual-reachable set still gives a cut of capacity zero. No assumption that capacities are integers is needed: the proof uses existence of a maximum and the absence of a residual augmenting path, not termination of an arbitrary sequence of augmentations.
Worked Networks
Worked Example: A Flow and a Cut of Value Five
Let \(V=\{s,a,b,t\}\), with directed arcs \(s\to a\) of capacity \(3\), \(s\to b\) of capacity \(2\), \(a\to b\) of capacity \(1\), \(a\to t\) of capacity \(2\), and \(b\to t\) of capacity \(3\). Start with zero flow and use the following residual paths.
| Path used | Bottleneck calculation | Flow value afterward |
|---|---|---|
| \(s\to a\to t\) | \(\min(3,2)=2\) | \(0+2=2\) |
| \(s\to b\to t\) | \(\min(2,3)=2\) | \(2+2=4\) |
| \(s\to a\to b\to t\) | \(\min(3-2,1,3-2)=\min(1,1,1)=1\) | \(4+1=5\) |
The final positive flows are \(f(s\to a)=3\), \(f(s\to b)=2\), \(f(a\to t)=2\), \(f(a\to b)=1\), and \(f(b\to t)=3\). At \(a\), inflow \(3\) equals outflow \(2+1=3\). At \(b\), inflow \(2+1=3\) equals outflow \(3\). The source sends \(3+2=5\), matching the sink’s receipt \(2+3=5\).
Both arcs leaving \(s\) are saturated, so no positive residual arc leaves \(s\); the residual-reachable set is \(S=\{s\}\). Its cut capacity is \(3+2=5\). The feasible flow has value \(5\), and the cut has capacity \(5\), so weak duality confirms that both are optimal.
Worked Example: Cancellation Creates the Second Route
Let \(V=\{s,a,b,x,y,t\}\). The arcs, all of capacity \(1\), are \(s\to a\), \(s\to b\), \(a\to x\), \(a\to y\), \(b\to x\), \(x\to t\), and \(y\to t\). First send one unit along \(s\to a\to x\to t\). The flow value is \(1\), and all three arcs on that route are saturated.
A second residual path is \(s\to b\to x\to a\to y\to t\). The step \(x\to a\) is the reverse residual arc for \(a\to x\), which currently carries one unit. The residual capacities along the path are \(1,1,1,1,1\): \(s\to b\), \(b\to x\), the reverse of \(a\to x\), \(a\to y\), and \(y\to t\). Thus the bottleneck is \(\min(1,1,1,1,1)=1\), and augmenting raises the value from \(1\) to \(1+1=2\).
After this update, \(f(s\to a)=1\), \(f(s\to b)=1\), \(f(a\to x)=0\), \(f(a\to y)=1\), \(f(b\to x)=1\), \(f(x\to t)=1\), and \(f(y\to t)=1\). Each internal vertex conserves flow: \(a\) receives \(1\) and sends \(1\); \(b\) receives and sends \(1\); \(x\) receives \(1\) and sends \(1\); and \(y\) receives and sends \(1\). The source and sink totals are both \(2\). Both arcs leaving \(s\) are saturated, so \(S=\{s\}\) has cut capacity \(1+1=2\). This verifies optimality and shows why reverse residual arcs matter: without cancelling \(a\to x\), the second unit could not reach the sink.
Worked Example: The Minimum Cut Need Not Be the Source Cut
Let \(V=\{s,a,b,t\}\), with capacities \(c(s\to a)=5\), \(c(s\to b)=4\), \(c(a\to t)=3\), \(c(b\to t)=2\), and \(c(a\to b)=2\). Send \(3\) units along \(s\to a\to t\) and \(2\) units along \(s\to b\to t\). The bottlenecks are \(\min(5,3)=3\) and \(\min(4,2)=2\), so the total value is \(3+2=5\).
At \(a\), the inflow is \(3\) and the outflow is \(3\); at \(b\), the inflow is \(2\) and the outflow is \(2\). The remaining forward residual capacities from \(s\) are \(5-3=2\) to \(a\) and \(4-2=2\) to \(b\), so both vertices are reachable. The arcs \(a\to t\) and \(b\to t\) are saturated, and no residual arc from \(a\) or \(b\) reaches \(t\). Hence the residual-reachable set is \(S=\{s,a,b\}\). The only arcs from this set to its complement are \(a\to t\) and \(b\to t\), so its cut capacity is \(3+2=5\). By weak duality the flow of value \(5\) is maximum and this cut is minimum. Notice that the cut \(\{s\}\) has capacity \(5+4=9\), which is larger.
A Common Mistake
In the flow-cut identity, incoming flow across the cut must be subtracted. For a concrete check, take \(V=\{s,a,b,t\}\) with arcs \(s\to a\), \(s\to b\), \(b\to a\), \(a\to t\), of capacities \(1,1,1,2\), respectively. Assign one unit to every arc. This is feasible: \(b\) receives and sends one unit, while \(a\) receives \(1+1=2\) and sends \(2\). Its value is \(2\).
For \(S=\{s,a\}\), the outgoing flow across the cut is \(f(s\to b)+f(a\to t)=1+2=3\), but the incoming flow is \(f(b\to a)=1\). The correct net flow is \(3-1=2\), as the identity requires. The cut capacity is \(c(s\to b)+c(a\to t)=1+2=3\), so weak duality gives \(2\le3\). The incorrect calculation that equates flow value with total outgoing flow would claim \(2=3\), because it ignores the incoming arc.
The theorem’s central proof pattern is useful well beyond these small networks: weak duality supplies a universal upper bound, while residual reachability turns a maximum flow into a cut that attains the bound. The constructed cut is not an arbitrary separation; its outgoing arcs are saturated and its incoming arcs carry zero flow.
Check Your Understanding
Use the flow-cut identity and residual reachability to justify your answers.
- Why does summing net outflow over the source side of a cut leave only arcs crossing that cut?
- What prevents a maximum flow from having a residual path from \(s\) to \(t\)?
- For a residual-reachable set \(S\), explain why every original arc directed from \(\overline{S}\) to \(S\) carries zero flow.
- In the third worked example, what is the capacity of the cut \(S=\{s,a\}\), and why is it not the cut extracted from the displayed flow?
- Can the theorem be applied when capacities are non-integers? Identify the part of the proof that does not depend on integrality.