# Flow network - minimum capacity cuts proof

Let's start out by reviewing max-flow min-cut, as well as the flow networks they operate on.

Let $G = (V,E)$ be a flow network. Prove a minimum cut is also a minimum-capacity cuts of $G$.

Thanks for any help, this problem has been throwing me for a loop!

Note: NOT homework, extra problems from our book I'm working through for exam preparation.

-
@Jesko Thanks for the formatting help! –  BHD Nov 18 '12 at 21:27

Here is a way to do this. Consider a max flow $f$ and the residual network $E_f$. From the max flow min cut theorem it is easy to get that $E_f$ doesn't contain any edge that goes from $S$ to $T$. Neither does it contain any edges from $S'$ to $T'$. Then it also has no edges going from $S \cup S'$ to $T \cap T'$.
But if no edge from $E_f$ crosses the cut $(S \cup S',T \cap T')$, then $$c(S \cup S', T \cap T') = f(S \cup S', T \cap T'),$$ and using the min cut max flow theorem once again we see that cut $(S \cup S', T \cap T')$ is also minimal.