# 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

## 1 Answer

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.

• Let me run through that logic real quick, I'm not nearly as good at this stuff as I should be, hence the practice. – BHD Nov 18 '12 at 21:36
• Seems to be correct! Thanks very much! My solution was a page long and still incorrect. Nice to see where I was going wrong. – BHD Nov 18 '12 at 22:34