I came across this interesting theoretical CS problem regarding max-flow networks in Algorithm Design (Kleinberg Tardos 2005):
The Forward-Edge-Only algorithm, which finds $s-t$ paths using only forward arcs where $f(e) < c_e$. Determine if the algorithm guarantees a flow of at least $1/k$ times the maximum flow for any input, where $k>1$. Prove or disprove this claim.
The correct answer is False, because I answered False and despite giving a wrong counterexample, I was given full marks.
This is the wrong counterexample I gave; it is wrong because the maxflow is not infinity despite the presence of $N$.
Consider a situation where the source can be connected directly to the sink through a path of capacity 1. There is a chance for the algorithm to choose that path arbitrarily. Then imagine another path going from source, to an intermediate node with capacity 1, then to the sink with an arbitrarily large number $N$. The algorithm terminates after finishing the short path and the path to the intermediate node, because there are no more paths consisting of arcs of ONLY $f(e) < c_e$, with $f(e)$ representing the flow and $c_e$ representing the capacity of edge $e$.
Since N could be infinity, hence giving the maximum flow the value of infinity, the guarantee of finding at least $\frac{1}{k}$ of maximum flow (i.e., finding a k-fraction of infinity) cannot hold.
How would I prove this claim to be false, or is it false?
