Intuitive background to the question $($not required to solve the question$)$:

The running of the Edmonds$-$Karp algorithm can be divided into "stages": in the first stage the algorithm finds paths of some length l$(1),$ in the second stage it finds paths of length l$(2)>$l$(1),$ in the third stage it finds paths of length l$(3)>$l$(2)$ and so on$.$

Each step has at most $|$E$|$ augmenting paths. This is when in each iteration the shortest path is chosen arbitrarily.

Thought: Can we get a better constraint on the number of augmenting paths at each stage? For example, by choosing a non$-$arbitrary shortest route.

In this question, you will prove that there are cases where Omega$(|$V$|^2)$ augmenting paths are needed to pass a stage, no matter how the shortest path is chosen.

For simplicity, prove this for the first step, but for two different l values.

formally:

Notation: For each flow network N $=($G $=($V$,$E$),$ c $,$ s $,$ t$)$ we denote by L$($N$)$ the length of the shortest path from s to t if one exists, or infinity otherwise.

Theorem: for every n$>=100$ there exists a flow network N $=($G $=($V$,$E$),$ c $,$ s $,$ t$)$ such that $|$V$|=$ n and the following conditions are met:

$(1)$ L$($N$)=$ l

$($l will be defined in each section separately$)$

$(2)$ The Edmonds$-$Karp algorithm on N necessarily runs for at least $($n$^2)/10$ iterations in which a path of length exactly l is chosen $($no matter how the shortest path is chosen in each iteration$).$

Instruction: If you need n to be divisible by a certain number, for example by $10,$ you can choose n that satisfies this.

A$.$ Present a flow network N that satisfies the theorem for l$=3$ and prove the theorem.

B$.$ Present a flow network N that satisfies the theorem for l$=($n$/10),$ without proof.