# Maximum number of augmenting paths in a network flow

Let's say we a have flow network with $m$ edges and integer capacities.

Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.

A good way to start thinking about this is to imagine that we know the maximum flow already. How can we figure the sequence of $m$ paths?

• Have you looked at runtime analyses of the Ford-Fulkerson algorithm? – Raphael Apr 14 '13 at 16:12
• The run-time analysis shows that the upper limit for the iterations in "the loop" is determined by the maximum capacity C. In the worst case scenario with the increments of 1 the algorithm roughly runs C times. – 372 Apr 14 '13 at 18:25
• why do you think this is true? – Sasho Nikolov Apr 14 '13 at 19:47
• This is a problem from one of the books. I think it is obvious that the problem is not trivial – 372 Apr 14 '13 at 20:15
• The Ford-Fulkense runtime analysis suggests the running time of O(N*f) where f is the largest flow in the network. This is natural because determination of a single path roughly takes O(N) and for integer maximum flow of f the algorithm iterates f times. So the non-trivial part is to prove that if paths were to be chosen in an optimal way the number of iterations would actually be N. – 372 Apr 14 '13 at 22:31 