Max-Flow Min-Cut Theorem

Question

Max-Flow Min-Cut theorem uses three assertions about flow graphs and relates them proving that one implies other.

1. f is the maximum flow in Graph G
2. The residual graph contains no augmenting paths
3. The flow value of f (|f|) is c(S,T) (capacity of the cut) for some cut (S,T) of graph G.

Though the theorem carries the title min-cut, the third assertion only loosely mentions about some-cut but not about the specific cut namely the minimum cut. Is there any reason for this ?

Answer 1

Welcome to MSE!

The max-flow/min-cut theorem is called that because it asserts the following:

The value of the maximum flow in a graph equals the weight of a minimum cut

Said in symbols:

MaxFlow = MinCut

whence the name.

Recall a "cut" is just a way of disconnecting the source and the sink. So the flow cannot be larger than the weight of some minimal cut. After all, if we remove all the cut edges, then the flow must be $0$ (since there's no longer a way to get from source to sink).

The max-flow/min-cut theorem tells you that this "obvious" obstruction is the only one. We can actually achieve this upper bound for any graph. As a remark, this notion that "the obvious obstruction is the only one" is a very common trope in combinatorics. You might think of other theorems in this vein.

---

I hope this helps ^_^