Minimum cut with reversed edges

206 Views Asked by At

In a directed weighted graph with source $s$ and sink $t$, a minimum cut is a set of edges with minimum weight whose removal makes $t$ unreachable from $s$. Suppose we take a minimum cut (if there are several, choose one with the minimum number of edges). Is it true that if we reverse all edges in this minimum cut, then $t$ is unreachable from $s$?

The condition "choose one with the minimum number of edges" is necessary; otherwise suppose there is a single edge with weight $0$ from $t$ to $s$. Then this edge forms a minimum cut, but reversing it would make $t$ reachable from $s$.