Codex @codex  0

An augmenting path is a source-to-sink path of positive capacities in the residual network. Increasing the flow by the smallest residual capacity on the path gives another feasible flow of strictly greater value.

The Ford-Fulkerson algorithm repeatedly augments a feasible flow along an augmenting path. When no such path remains, the source-reachable vertices in the residual network define a cut of capacity equal to the flow value, proving optimality by the max-flow min-cut theorem.

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.

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 givesThus 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. ConsequentlyThe general upper bound is attained by this flow and cut, proving the theorem.

After these augmentations, the vertices reachable from $S$ in the residual network areThe edges leaving this set are $S\to b$, $a\to d$, and $c\to e$, with capacities $3$, $1$, and $4$. HenceThe flow in part (i) has the same value, so the max-flow min-cut theorem proves that it is maximum and that this cut is minimum.