The max-flow min-cut theorem equates the maximum value of an 
-
network flow with the minimum
capacity of an 
-
cut in a directed
graph. Let 
be a directed network flow graph with source 
,
sink 
, and nonnegative edge capacities 
.
An 
-
flow 
assigns each graph edge a value
satisfying 
and conserves flow at every graph
vertex other than 
and 
. Its value 
is the net amount leaving 
.
An 
-
cut is a partition 
with 
and 
. Its capacity is the
sum of the capacities of the
edges directed from 
to 
. With these definitions,
 |
Thus every cut gives an upper bound on the value of a flow, and there is always a flow and a cut attaining the same value (Ford and Fulkerson 1962; Skiena 1990, p. 178).
The theorem underlies the augmenting path method: when the residual network contains no path from 
to 
, the vertices reachable from
determine a minimum cut. If all capacities
are integers, a maximum flow
can be chosen with integer values on every graph
edge.
