Prove that if the residual graph doesn't contain a path from $u$ to $v$, then $e=(u,v)$ crosses some minimum cut

47 Views Asked by At

Prove: given a flow network $N=(G,s,t,c)$ with a maximum flow $f^*$ and a given edge $e=(u,v)$, then there's no path from $u$ to $v$ in $N_{f^*}$.

I've seen this thread, but the only answer there is wrong. I tried building a minimum cut myself, saying $S$ is all the vertices which are accesible from $u$, but I can't prove this is even a valid s-t cut.