# Max-flow min-cut

## Max-flow min-cut theorem

Let $G=(V,A)$, $s,t\in V$, and for $a\in A$ let $u(a)$ and $f(a)$ be real values such that $0\leq f(a)\leq u(a)$ and $f$ is a feasible $(s,t)$-flow. Then the following three statements are equivalent:

1. The flow value of $f$ is maximum among all feasible $(s,t)$-flows.
2. There is a saturated cut.
3. There is no flow-augmenting path from $s$ to $t$.

## Proof

First suppose there is no flow-augmenting path from $s$ to $t$. Let $S$ denote the set of all nodes reachable from $s$ via flow-augmenting paths, and let $T:=V\setminus S$. Then we have $s\in S$ and $t\in T$. Obviously, $(S,T)$ is saturated.

Next suppose there is a saturated cut. No flow $f'$ can carry more units of flow value from $s$ to $t$ than the capacity of any $(s,t)$-cut allows. Consequently, $f$ is maximum.

Finally suppose $f$ is maximum. Clearly, then a flow-augmenting path from $s$ to $t$ cannot exist.