2
$\begingroup$

I have to show that a maximum flow in a network $G = (V;E)$ can always be found by a sequence of at most $|E|$ augmenting paths. A hint that was given to me was to determine the paths after finding the maximum flow.

Appreciate all the help. Thanks!

  • 1
    Perhaps you can show that every augmenting path can be chosen so as to increase the number of saturated edges.2012-11-06

1 Answers 1