Giving an upper bound on the length of any augmenting path G'

Question

Let $G = (V, E)$ be a bipartite graph with vertex partition $V = L∪R$, and let $G'$ be its corresponding flow network. Give a good upper bound on the length of any augmenting path found in $G'$ during the execution of FORD-FULKERSON algorithm.

Answer 1

An obvious upper bound is $n - 1$ (where $n = |G| = |V|$ is the number of vertices). It holds for any non-closed simple path in a graph on $n$ vertices, because simple path contains every vertex at most once. The original Ford—Fulkerson method operates with simple paths found by depth first search. (Further modifications operate with paths found by breadth first search or provided by data structure like dynamic tree, but still all these paths are simple.)

On the other hand this bound is easily reachable when $G \cong P_n$, i. e. the graph $G$ is a path itself, and the end vertices of this path are source and sink.

Yes, this case is rather special. But we can get $\Theta(n)$ length of every augmenting path (if we are not lucky) for $\Omega(n)$ augmenting paths.