1
$\begingroup$

Let $G = (V,E)$ be a flow network. Let $e = (u,v)$ be an edge in $E$ and let $f$ be a maximum flow in $G$. Prove or Disprove:

If the residual graph $G_f$ contains no directed path from $u$ to $v$ then $e$ crosses some minimum cut in $G$.

I might be mistaken, but I think that the statement is true. However, I've failed to prove that such a minimum cut actually exists.

I've also tried to assume by contradiction that $e$ doesn't cross any minimum cut in $G$. It follows that for every cut $(S,T)$ that $e$ crosses, the residual graph $G_f$ contains some edge $e'$ that crosses the cut (and this edge is obviously not saturated). But how does it help us to build a path from $u$ to $v$ in $G_f$ ?

$\endgroup$
1
$\begingroup$

I believe you can disprove this by considering this graph (with all capacities = 1): s->A, A->B, A->C, B->t, C->t

Note that this flow network has exactly one minimal s-t cut: {s}, {A,B,C,t} with capacity 1. The only edge which crosses this cut is s->A. Now take any maximal flow in this network, calculate the residual graph and continue from there.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.