A Question about a Question related to Graph Theory and Maximum Flow

Question

The following question is from the book "Introduction to Algorithms" By Cormen and three other authors.

$26.2-10$
Show how to find a maximum flow in a network $G = (V,E)$ by a sequence of at most $|E|$ augmenting paths. (Hint: Determine the paths after finding the maximum flow.)

I find this question confusing because the hint contradicts the question. Is it asking you to find the maximum flow in a graph? or is it asking you to find a path?

Recall that for a given flow graph $G$ there might be several flows that yield the maximum flow. Is this question asking you to find all the flows that produce a maximum flow? Do you think this question is properly worded?

Bob

Answer 1

It's asking you to prove that there exists a sequence of $|E|$ augmenting paths that yields the maximum flow.

The hint suggests: suppose you already knew the maximum flow. Then use that information to choose $|E|$ augmenting paths, that will yield that maximum flow.

Yes, this sounds weird. Obviously what you have proven will not be useful as a maximum-flow algorithm (you would need to know the maximum flow already, so it's no use in computing the maximum flow). Think of it as proving a theoretical fact, rather than trying to design a useful algorithm.