# shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/).

Everything in the first part of the proof (The section Monotonically increasing path length) makes sense. However, the last part of it is not very convincing (the part I have highlighted with red).

Can someone convince me that it is true that the fact that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $$O(E)$$". It is no wonder why that you doubt that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $$O(|E|)$$".
The time bound of $$O(|E|)$$ has nothing to do with the fact that "the shortest path increases monotonically in the residual graph".
It takes $$O(E)$$ time to perform one iteration of Edmonds-Karp algorithm, since what it does is mostly a breadth-first search.
(It takes $$O(|V| + |E|)$$ time for a breadth-first search on a general graph. However, in the case of finding the maximum flow in a flow network, we assume the given network is connected or there is at least one edge incident to every vertex usually. That is, $$|E|\ge |V|-1$$ or $$2|E|\ge|V|$$. Then $$O(|V|+|E|)=O(|E|)$$)
• so in summary, the BFS runs in $O(|V|+|E|)$ time on a general graph, but in a flow network graph it can be proved that BFS runs even faster: $O(|E|)$. In the proof of the edmon-karp time complexity, the author of the proof assumed the reader knew this fact about BFS having a faster running time if "paths are monotonically increasing in a flow network", in that it was common knowledge; therefore he didn't include that information as the explanation for the implication that "paths are monotonically increasing in a flow network" implies "bound on one iteration of Edmonds-Karp algorithm to O(|E|)" Aug 11, 2022 at 8:39