Max-flow Min-cut Theorem (Theorem 24.6 in textbook):
If f is a flow in a flow network G = (V, E) with source s and sink t, then the following conditions
are equivalent:
• f is a maximum flow in G.
• The residual network Gf contains no augmenting paths.
• |f | = c(S, T ) for some cut (S, T ) of G
Now you can utilize the theorem directly without proof to solve the following question. Let
G = (V, E) be an s-t flow network with integer capacity ce > 0 on each edge e ∈ E. We say
that edge e ∈ E is fully saturated if the flow uses its full capacity in every maximum s-t flow in G.
Show that if e is not saturated in some maximum flow, then e does not cross any min cut from the
set containing s to the set containing t.
