2

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

Robert777
  • 199
  • 7

1 Answers1

1

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.

Yodan Tauber
  • 111