Max Flow / Min Cut Theorem

For any flow f, the following are equivalent

(1) |f| = c(S,T) for some cut S,T (a min cut)

(2) f is a maximum flow

(3) f admits no augmenting path

Proof:

(1) ? (2): corollary to lemma 2

(2) ? (3): lemma 1

Previous slide

Next slide

Back to first slide

View graphic version