# Operation of the Ford–Fulkerson algorithm given an almost maximum flow [closed]

I have been assigned the question:

Let $$G$$ be a flow network and $$f^*$$ be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network $$G'$$ constructed by increasing the capacity of exactly one of $$G$$'s edges by one.

Using the maximum-flow and minimum-cut theorem, argue that if we run the Ford-Fulkerson algorithm on $$G'$$ with $$f^*$$ as the initial flow, the while-loop shall terminate in at most one iteration.

But I feel like the loop can run more than once...

Considering a base case where $$G$$ has one edge between the sink and source with a capacity of 1.

Then $$G'$$ will have one edge with a capacity of 2.

So then when we run the Ford–Fulkerson algorithm with an initial flow of $$f^* = 1$$, the first loop will leave a residual graph with an edge with a capacity of 1, and therefore the loop will run for a second time.

• So what's your question? – David Richerby Nov 14 '16 at 8:16
• How many times will the Ford-Fulkerson Algorithm loop if there are ONLY source and sink vertices, and the inital augmented flow is < the capacity? (regarding my example) – Eric Nelson Nov 14 '16 at 9:07
• This is a question-and-answer site, so we need you to explicitly articulate a specific question that you want answered. – D.W. Dec 4 '16 at 3:11

You are interpreting the question too literally. The question claims that only one augmentation step will be performed. In your example, we augment $f^*$ by pushing one more unit of flow, and then we reach the maximum flow of the updated network.