= Solution
A feasible flow assigns $f_{ij}$ to each directed edge so that
$$
0\leq f_{ij}\leq C_{ij}
$$
and inflow equals outflow at every vertex other than the source and sink. Its value $|f|$ is the net outflow from the source. For a set $S$ containing the source but not the sink, the associated cut has capacity
$$
C(S,V\setminus S)
=\sum_{i\in S,\,j\notin S}C_{ij}.
$$
The <max-flow min-cut theorem> states
$$
\boxed{
\max_f|f|=\min_{S\ni s,\,t\notin S}C(S,V\setminus S)}.
$$
For every flow and cut, conservation at vertices inside $S$ gives
$$
|f|=f(S,V\setminus S)-f(V\setminus S,S)
\leq C(S,V\setminus S).
$$
This proves the weak inequality.
A maximum flow exists because the feasible-flow polytope is nonempty, closed, and bounded. Form its residual graph: a forward edge has residual capacity $C_{ij}-f_{ij}$, and a reverse edge has residual capacity $f_{ij}$. If the residual graph contained a source-to-sink path, augmenting by the smallest positive residual capacity on that path would increase the flow, contradicting maximality.
Let $S$ be the vertices reachable from the source in the residual graph. The sink is not in $S$. Every original edge from $S$ to its complement is saturated, and every original edge from the complement into $S$ carries zero flow; otherwise the appropriate residual edge would make its other endpoint reachable. Hence
$$
|f|=f(S,V\setminus S)-f(V\setminus S,S)
=C(S,V\setminus S).
$$
The maximum flow therefore equals the capacity of this cut, completing the proof.
Back to article page
