Given a network flow and there exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow.

I've had this questions with true or false and I thought it was false but apparently it is true. Can someone please explain me how this is possible?


1 Answer 1


Since you just have to satisfy the conservation of flow property and capacity property. You can consider the following example:

$V = \{s,t,u,v\}$ and $E = \{(s,t), (u,s), (u,v), (v,u)\}$ with each edge of capacity 1.

You can send a flow of 1 via $(u,v)$, $(v,u)$, and $(s,t)$. It follows all properties of a valid flow. It does not have a path from $s$ to $u$. Also, the flow via $(u,v)$ is at its full capacity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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