Max-flow min-cut

Max-flow min-cut theorem

Let [math]\displaystyle{ G=(V,A) }[/math], [math]\displaystyle{ s,t\in V }[/math], and for [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be real values such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] and [math]\displaystyle{ f }[/math] is a feasible [math]\displaystyle{ (s,t) }[/math]-flow. Then the following three statements are equivalent:

1. The flow value of [math]\displaystyle{ f }[/math] is maximum among all feasible [math]\displaystyle{ (s,t) }[/math]-flows.
2. There is a saturated cut.
3. There is no flow-augmenting path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math].

Proof

First suppose there is no flow-augmenting path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math]. Let [math]\displaystyle{ S }[/math] denote the set of all nodes reachable from [math]\displaystyle{ s }[/math] via flow-augmenting paths, and let [math]\displaystyle{ T:=V\setminus S }[/math]. Then we have [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\in T }[/math]. Obviously, [math]\displaystyle{ (S,T) }[/math] is saturated.

Next suppose there is a saturated cut. No flow [math]\displaystyle{ f' }[/math] can carry more units of flow value from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] than the capacity of any [math]\displaystyle{ (s,t) }[/math]-cut allows. Consequently, [math]\displaystyle{ f }[/math] is maximum.

Finally suppose [math]\displaystyle{ f }[/math] is maximum. Clearly, then a flow-augmenting path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] cannot exist.