Residual Arcs and the Flow-Cut Identity
A maximum flow and a minimum cut have the same value, but a fixed maximum flow can reveal more than one minimum cut. The key is to inspect not only which original arcs cross a cut, but also which directions still have positive residual capacity. A cut is minimum precisely when no positive-residual arc leaves its source side.
Throughout, a network is a finite directed graph with source \(s\), sink \(t\), and nonnegative capacity \(c(e)\) on each arc \(e\). A feasible flow \(f\) satisfies \(0\le f(e)\le c(e)\) and flow conservation at every vertex other than \(s,t\). Its value is denoted \(|f|\). An \(s\)-\(t\) cut is a partition \((S,\overline S)\) of the vertices with \(s\in S\) and \(t\notin S\). Its capacity \(c(S,\overline S)\) is the sum of capacities of original arcs directed from \(S\) to \(\overline S\). A minimum cut is an \(s\)-\(t\) cut of smallest capacity.
A positive forward residual arc represents capacity still available on an original arc. A positive reverse residual arc represents flow that could be cancelled. Both types matter when testing whether a residual arc leaves a cut's source side.
Proof. Write \(f(S,\overline S)\) for the sum of flow on original arcs from \(S\) to \(\overline S\), and \(f(\overline S,S)\) for the sum on original arcs in the other direction. Summing flow conservation over the vertices of \(S\) cancels contributions from arcs internal to \(S\). Since \(s\in S\) and \(t\notin S\), the remaining net flow out of \(S\) is \(|f|\). Thus \(|f|=f(S,\overline S)-f(\overline S,S)\). Subtract this from \(c(S,\overline S)\) and rearrange: \(c(S,\overline S)-|f|=c(S,\overline S)-f(S,\overline S)+f(\overline S,S)\). The first difference is the sum of forward residual capacities on arcs from \(S\) to \(\overline S\). Each original arc from \(\overline S\) to \(S\) contributes a reverse residual arc from \(S\) to \(\overline S\), with residual capacity equal to its flow. These are exactly the terms in the displayed identity. \(\square\)
The Residual Criterion for Minimum Cuts
Proof. The max-flow min-cut theorem states that the value of a maximum flow equals the capacity of a minimum cut. In particular, an \(s\)-\(t\) cut is minimum exactly when its capacity equals \(|f|\). By the flow-cut identity, \(c(S,\overline S)-|f|\) is a sum of nonnegative residual capacities of arcs leaving \(S\). This sum is zero exactly when every such residual capacity is zero, or equivalently when no positive-residual arc leaves \(S\). Therefore the cut is minimum exactly under the stated condition. \(\square\)
The theorem tests a particular source side \(S\). To locate one minimum cut, begin at \(s\) and follow every positive-residual arc that leaves a vertex already reached. The set reached cannot contain \(t\), because the flow is maximum: a residual path from \(s\) to \(t\) would allow an augmentation and would contradict maximality. When the search stops, no positive-residual arc leaves the reached set. The theorem therefore says that this set is the source side of a minimum cut.
Proof. The theorem proves that every set with these properties is the source side of a minimum cut, and that every minimum cut has these properties. In particular, let \(R\) be the set of vertices reachable from \(s\) by positive-residual arcs. If \(S\) is the source side of a minimum cut, then \(R\subseteq S\): every vertex on a residual path starting at \(s\) must remain in \(S\), since a first step out of \(S\) would be a positive-residual arc leaving it. Also \(t\notin R\), since \(f\) is maximum. Thus \(R\) gives the smallest source side among these cuts, though other minimum-cut source sides may contain additional vertices. \(\square\)
Finding and Comparing Minimum Cuts
Worked Example: Three Minimum Cuts from One Maximum Flow
Consider the directed network with vertex set \(\{s,a,b,t\}\) and 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\). Send flow equal to capacity on every arc.
At \(a\), inflow is \(3\) and outflow is \(1+2=3\). At \(b\), inflow is \(2+1=3\) and outflow is \(3\). The flow value is \(3+2=5\), the total flow leaving \(s\). Every original arc is saturated, so the positive residual arcs are just the reverse arcs: \(a\to s\) with capacity \(3\), \(b\to s\) with capacity \(2\), \(b\to a\) with capacity \(1\), \(t\to a\) with capacity \(2\), and \(t\to b\) with capacity \(3\). No positive-residual arc leaves \(s\), so no residual \(s\)-\(t\) path exists. The flow is maximum.
To find all minimum cuts, choose a source side containing \(s\) and excluding \(t\). If it contains \(b\), the residual arc \(b\to a\) forces it to contain \(a\). If it contains \(a\), there is no residual arc from \(a\) to \(b\) or \(t\), so \(b\) need not be included. The three possible source sides are therefore \(\{s\}\), \(\{s,a\}\), and \(\{s,a,b\}\).
Their capacities are, respectively, \(3+2=5\); \(2+1+2=5\); and \(2+3=5\). Each equals the maximum flow value, confirming that all three cuts are minimum. The residual-arc condition finds them without needing to enumerate arbitrary cuts.
Worked Example: Tracing Residual Reachability
Use the same five arcs, but let their capacities be \(c(s,a)=4\), \(c(s,b)=2\), \(c(a,b)=1\), \(c(a,t)=2\), and \(c(b,t)=3\). Set the flows to \(f(s,a)=3\), \(f(s,b)=2\), \(f(a,b)=1\), \(f(a,t)=2\), and \(f(b,t)=3\). At \(a\), both inflow and outflow are \(3\); at \(b\), both are \(3\). The flow value is \(3+2=5\).
The positive residual arcs are \(s\to a\) of capacity \(4-3=1\), \(a\to s\) of capacity \(3\), \(b\to s\) of capacity \(2\), \(b\to a\) of capacity \(1\), \(t\to a\) of capacity \(2\), and \(t\to b\) of capacity \(3\). The reachability search is:
| Stage | Queue before scanning | Residual arcs scanned | New vertices |
|---|---|---|---|
| Start | \([s]\) | From \(s\): \(s\to a\) positive; no positive \(s\to b\) | \(a\) |
| Next | \([a]\) | From \(a\): \(a\to s\) positive; no positive arc to \(b\) or \(t\) | None |
| Finish | Empty | No unscanned reached vertices | None |
Thus the reached set is \(R=\{s,a\}\), and \(t\) is not reached. The cut with source side \(R\) has capacity \(c(s,b)+c(a,b)+c(a,t)=2+1+2=5\), equal to the flow value. The larger source side \(\{s,a,b\}\) also has no outgoing positive-residual arc, since its only original arcs crossing to \(t\) are saturated and the residual arcs \(t\to a,t\to b\) point into the source side. Its cut capacity is \(c(a,t)+c(b,t)=2+3=5\). Both are minimum cuts.
Check: the residual search reached \(a\) because \(c(s,a)-f(s,a)=4-3=1>0\), but did not reach \(b\), because \(c(s,b)-f(s,b)=2-2=0\). This agrees with \(R=\{s,a\}\).
A Common Mistake: Ignoring Reverse Residual Arcs
Worked Example: A Saturated Forward Cut That Is Not Minimum
Let the directed network have vertices \(\{s,b,a,t\}\) and arcs \(s\to b\), \(b\to a\), and \(a\to t\), each of capacity \(2\). Send flow \(2\) on each arc. Conservation holds at \(b\) and \(a\), and the flow value is \(2\). Since the only \(s\)-\(t\) route is saturated, this flow is maximum.
Consider the source side \(S=\{s,a\}\). Its original arcs directed out are \(s\to b\) and \(a\to t\), both saturated. A mistaken test that checks only whether an original forward arc crossing the cut has unused capacity would therefore report no obstruction. But the original arc \(b\to a\) carries flow \(2\), so its reverse residual arc \(a\to b\), of capacity \(2\), leaves \(S\). The residual criterion correctly rejects this cut as minimum. Its capacity is \(2+2=4\), which exceeds the maximum flow value \(2\).
For comparison, the cut with source side \(\{s,b\}\) has capacity \(c(b,a)=2\), equal to the flow value, and is minimum. Its crossing arc \(b\to a\) is saturated, while the reverse residual arc \(a\to b\) points into its source side. Thus it has no positive-residual arc leaving it.
The distinction is important: the capacity of a cut counts only original arcs directed from its source side to its other side, while the flow value is net flow across the cut. Flow on an original arc directed back across the cut reduces that net flow. The reverse residual arc records exactly this contribution. A correct test must examine every positive-residual arc leaving the proposed source side, including reverse residual arcs.
For a fixed maximum flow, the residual network therefore gives both a certificate and a way to organize the minimum cuts. Any source side containing \(s\), excluding \(t\), and closed under outgoing positive-residual arcs is minimum. The vertices reachable from \(s\) must belong to every such source side; additional vertices may be included only when doing so still creates no outgoing positive-residual arc.
Check Your Understanding
Use the flow-cut identity and the residual-arc criterion to answer these questions.
- Why does a zero sum of outgoing residual capacities imply that each outgoing residual capacity is zero?
- For the first worked example, why must any valid source side containing \(b\) also contain \(a\)?
- In the second worked example, what residual capacity allows the search from \(s\) to reach \(a\), and why can it not then reach \(b\)?
- Explain why a reverse residual arc can leave a source side even when every original forward arc crossing that cut is saturated.
- For a fixed maximum flow, prove that every vertex reachable from \(s\) belongs to the source side of every minimum cut.