= Max-flow min-cut theorem
{title2=$\max_f|f|=\min_{S:s\in S,\,t\notin S}c(S,V\setminus S)$}
{wiki}
For a finite <flow network> with finite nonnegative real <flow network edge capacities>, the greatest <strength of a flow> of a <feasible flow> equals the least <cut capacity> of a source-to-sink <cut of a flow network>:
$$
\max_{f\text{ feasible}}|f|
=\min_{S\subseteq V:\,s\in S,\,t\notin S}
\sum_{(u,v)\in E:\,u\in S,\,v\notin S}c_{uv}.
$$
For a <maximum flow>, the <vertices> reachable from the source in the <residual network> define a <minimum cut> whose outgoing original <edges> are saturated and whose incoming original <edges> carry zero <flow>.https://courses.csail.mit.edu/6.854/21/Notes/n06-flow.html[Karger, MIT 6.854 Notes 6, maximum-flow optimality conditions]{ref}
Why is a <cut of a flow network> an upper bound? Sum <flow conservation> on its source side $S$. Internal <edge> contributions cancel, leaving
$$
|f|=\sum_{(u,v)\in E:\,u\in S,\,v\notin S}f_{uv}
-\sum_{(u,v)\in E:\,u\notin S,\,v\in S}f_{uv}
\leq\sum_{(u,v)\in E:\,u\in S,\,v\notin S}c_{uv}
=c(S,V\setminus S).
$$
Only directed <edges> leaving $S$ contribute to <cut capacity>. Directed <edges> entering $S$ are subtracted in net <flow>, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is <weak duality>; the theorem says the bound is attained, an instance of <strong duality>. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.
In the running <flow network>, the two internal <vertices> give four possible source sides. For $S=\{s\}$, the <cut capacity> is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming <edge> $a\to b$ contributes nothing to that <cut capacity>. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the <minimum cut> has <cut capacity> $5$, matching the explicitly computed <maximum flow>.
\Image[/max-flow-cut-certificate.png]
{title=Maximum flow of value five and two minimum-cut certificates}
{description=Labels show flow/capacity on each directed edge. The shaded source sides give cuts of capacities three plus two and two plus one plus two, both equal to the flow value.}
Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses <graph paths> carrying nonnegative amounts; the <residual reachability certificate for maximum flow> below gives the finite directed <flow network> proof used here.https://doi.org/10.4153/CJM-1956-045-5[Ford and Fulkerson, Maximal Flow Through a Network, Canadian Journal of Mathematics 8 (1956), pp. 399–404]{ref}
Back to article page
