Proof (continued) (3)=(1): Suppose that f admits no augmenting paths Define s=lvev: there exists a path in Gr from s to v) and let t=v-s observe that s e s and te t and thus (S, T)is a cut. Consider any vertices u E S and vE T path in g We must have cr(u, v)=0, since if cr(u, v)>0, then E S not v E T as assumed. Thus, f(u,v)=c(u, v), since cr(u,v) cu, v)f(u, v). Summing over all u E S and E ields f(S,T)=c(S, 1), and since f =f(S, T), the theorem allOWS c 2001 by Charles E Leiserson Introduction to Agorithms Day 40 L23.4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.4 Proof (continued) (3) ⇒ (1): Suppose that f admits no augmenting paths. Define S = {v ∈ V : there exists a path in Gf from s to v}, and let T = V – S. Observe that s ∈ S and t ∈ T, and thus (S, T) is a cut. Consider any vertices u ∈ S and v ∈ T. We must have cf (u, v) = 0, since if cf (u, v) > 0, then v ∈ S, not v ∈ T as assumed. Thus, f(u, v) = c(u, v), since cf (u, v) = c(u, v) – f(u, v). Summing over all u ∈ S and v ∈ T yields f(S, T) = c(S, T), and since | f | = f(S, T), the theorem follows. ss uu vv S T path in Gf