Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 35 / 3 / b

Start with zero flow and apply the Ford-Fulkerson algorithm. The following augmenting paths and bottlenecks use the capacities in the original PDF diagram:For example, the second path is limited by the remaining capacity two on $6\to 8$ and by capacity two on $5\to 6$. After the third augmentation, $7\to 8$ has residual capacity one; the fourth path supplies it through $5\to 4\to 6\to 7$. Every displayed increment is the smallest residual capacity of its path.

The resulting arc flows areHere $uv$ denotes $u\to v$. These satisfy every capacity bound and flow conservation. The final residual network has source-reachable set $S=\{1,2,3,5\}$. Its outgoing arcs are $2\to 4$, $5\to 4$, $5\to 6$ and $5\to 7$, with capacities $2,1,2,1$, all saturated. ConsequentlyThis is a minimum cut, and the equal flow and cut values certify optimality by the max-flow min-cut theorem. The cut immediately before node eight also has capacity six, so the minimum cut is not unique.