1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.