Minimum cut

A minimum cut is a cut of a flow network of least cut capacity for the prescribed source $s$ and sink $t$. The max-flow min-cut theorem equates that least cut capacity with the greatest flow value.^[ref]

To certify a particular minimum cut, exhibit a feasible flow whose flow value equals its cut capacity. Every feasible flow is bounded above by every cut capacity, so this single equality proves both optimalities.^[ref]

In the running example, the four possible source sides $\{s\}$, $\{s,a\}$, $\{s,b\}$ and $\{s,a,b\}$ have cut capacities $5,5,6,5$, respectively. The feasible flow of flow value $5$ therefore certifies three different minimum cuts. A minimum cut need not be unique; the optimum cut capacity is the same for all of them. Merely saturating many edges does not give this certificate: flow conservation and the particular cut of a flow network must also be checked.

On $\{0,\dots ,m{\}}^2$, give an adjacent edge capacity equal to the larger endpoint distance $|i_1-i_2|$ from the diagonal. The set $S=\{i_1<i_2\}$ has $2m$ outgoing edges: two at each interior diagonal vertex and one at each endpoint. Every such edge has capacity one. Thus any flow from above to below the diagonal is at most $2m$; a feasible path decomposition attaining this value certifies optimality by weak duality.