= Solution
The <max-flow min-cut theorem> states that in a finite <flow network>, the maximum value of a feasible source-to-sink flow equals the minimum capacity of a source-to-sink <cut of a flow network>[cut].
First consider any feasible flow $f$ and any cut $(A,V\setminus A)$ with $S\in A$ and $T\notin A$. Summing <flow conservation> over the vertices in $A$ cancels all contributions from edges internal to $A$ and gives
$$
|f|
=\sum_{u\in A,v\notin A}f(u,v)
-\sum_{u\notin A,v\in A}f(u,v)
\leq\sum_{u\in A,v\notin A}c(u,v)
=c(A,V\setminus A).
$$
Thus every flow value is at most every cut capacity.
A maximum flow exists because the feasible flows form a nonempty compact subset of a finite-dimensional Euclidean space and the flow value is continuous. Let $f$ be maximum and form its <residual network>. If there were an <augmenting path> from $S$ to $T$, increasing $f$ by the path's positive bottleneck capacity would contradict maximality. Let $A$ be the set of vertices reachable from $S$ in the residual network. Then $T\notin A$. Every original edge from $A$ to its complement is saturated, while every original edge entering $A$ carries zero flow; otherwise the corresponding forward or reverse residual edge would make its other endpoint reachable. Consequently
$$
|f|
=\sum_{u\in A,v\notin A}c(u,v)
=c(A,V\setminus A).
$$
The general upper bound is attained by this flow and cut, proving the theorem.
Back to article page
