I have to prove that the running time of the Edmond-Karp-Algorithm is $\Theta({m^2}n$) by providing a family of graphs, where the Edmond-Karp-Algorithm has a running time of $\Omega({m^2}n$).
I have to solve it by constructing a family of graphs, where at least one edge is saturated by $\Omega(n)$ augmenting paths. Then replace this edge by a suitable graph containing $\Omega(m)$ edges and add extra vertices to adapt the lengths of other paths in the graph.
Any help will be appreciated Thanks