# Maximum flow in a network proof

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!

-
Welcome to math.SE community! Please, acquaintance yourself with the FAQ, it is really helpful (among others there are some tips for how to make your questions/answers readable). Also, from the wording of your question I suspect that it might be a homework problem. Please note, that there is a (homework) tag, it will cause that you will get not only solution, but probably also a lot of useful hints how to work it out yourself. On the other hand, homework assignments without the (homework) tag are treated really badly. Good luck! –  dtldarek Nov 6 '12 at 11:12
Perhaps you can show that every augmenting path can be chosen so as to increase the number of saturated edges. –  Gerry Myerson Nov 6 '12 at 11:20

I'll reformulate the statement a bit to avoid ambiguity (although it is possible that the ambiguity is only in my head due to my poor knowledge of English): in any network $G=(V, E)$ there exists a maximum flow $f$ that can be found by a sequence of at most $|E|$ augmenting paths.
One way to prove that is by considering a maximum flow $f$ that has the minimal possible value of $\sum_{u,v \in V} |f(u, v)|$. Such a flow exists, because the space of all max flows is compact and the function $f \to \sum_{u,v \in V} |f(u, v)|$ is continuous.
Now consider a new graph $G'=(V, E')$ where $E'=\{(u,v)|f(u, v)>0\}$. It is easy to prove that since $\sum_{u,v \in V} |f(u, v)|$ is minimal, this graph $G'$ is acyclic. Now it is quite easy to see that flow $f$ can be found by a sequence of at most $|E'|$ augmenting paths whose edges belong to $E'$.
NOTE: about that ambiguity that I mentioned earlier. If the statement actually means that any maximum flow can be found by a sequence of at most $|E|$ augmenting paths, then it is simply not true. To build a counterexample one can just take any network and attach to it a new cycle (somewhere on the side) with huge edge capacities, and send a huge flow along that cycle. To build such a flow one would need to augment the flow a huge number of times.