Max-flow. min-cut theorem Theorem. The following are equivalent 1. f=c(S, n) for some cut(S, T) 2. fis a maximum flow 3. f admits no augmenting paths Proof (1)→(2): Since f≤c(S, T)for any cut(S,T)(by the corollary from Lecture 22), the assumption that f=cs, T) implies that f is a maximum flow (2)=(3): If there were an augmenting path, the flow value could be increased, contradicting the maximality of f. c 2001 by Charles E Leiserson Introduction to Agorithms Day40L23.3© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.3 Max-flow, min-cut theorem Theorem. The following are equivalent: 1. | f | = c(S, T) for some cut (S, T). 2. f is a maximum flow. 3. f admits no augmenting paths. Proof. (1) ⇒ (2): Since | f | ≤ c(S, T) for any cut (S, T) (by the corollary from Lecture 22), the assumption that | f | = c(S, T) implies that f is a maximum flow. (2) ⇒ (3): If there were an augmenting path, the flow value could be increased, contradicting the maximality of f