Network flow - does edge lie on directed path

51 Views Asked by At

a) Let $f$ be a flow network $(G, c, s, t)$ and $e$ an edge such that $f(e) > 0$. Then there must exist a directed path from $s$ to $t$ that contains the edge $e$.

b) Let $f$ be a flow network $(G, c, s, t)$ and $C$ a cut in that network. If for all $e \in C$ is true that $f(e) = c(e)$ then $f$ must be a maximum flow.

Is a) and b) true or false, if so why?

My arguments that a) is True:

If $f(e) > 0$ and no path from $s$ to $t$ would contain that edge, then we would break Kirchhoff's laws.

b) I'm not really sure how to argument on that one. But I think it's false because $C$ can be any cut.