= 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>.<Graph Theory by Reinhard Diestel/Flows (author-hosted chapter preview)>[Graph Theory by Reinhard Diestel; Diestel, Flows, §6.2, Theorem 6.2.2, printed p. 159]{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.<Algorithms, 4th edition by Robert Sedgewick and others/FordFulkerson.java>[Algorithms, 4th edition by Robert Sedgewick and others; Sedgewick and Wayne, FordFulkerson.java, check method, lines 180–209: feasibility, source/sink membership and equality of values]{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.
Back to article page
