Peer Sheet 5

P5.1 Flows and Cuts

We found an $s$-$t$ cut $(S,T)$ with $\mathrm{cap}(S,T)=12$ and a flow $f$ with $\mathrm{val}(f)=12$. Since every flow value is at most the capacity of every $s$-$t$ cut, we have $12=\text{val}(f)\le OPT\le \text{cap}(S,T)=12$ (using the Maxflow-Mincut Theorem) so $OPT=12$, and $f$ is a maximum flow