Max flow bottleneck approach flow after k iterations

Question

This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why.

Given a network flow $(G,c)$ over graph $G(V,E) $.

Assume we run Edmonds-Karp algorithm to find the max flow with the Max Bottleneck approach.

After $\frac{|E|}{2}$ iterations we decide to stop the algorithm. What is true about the current flow?

1. The flow we found is a maximum flow.

2. The flow we found is at least $\frac{3}{4}$ of the max flow.

3. The flow we found is at least $\frac{1}{2}$ of the max flow.

4. The flow we found could be be as small as we like depending on $c $ and $G$.

5. all above answers are wrong.

In class we proved a lemma that says this ($f^*$ is the max flow) $$ \left|f^{*}\right|-\left|f^{k}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{k}\left|f\right|\implies $$ $$ \left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right| $$ now we can use Taylor's approximation for the binomial function and get that: $$ \left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\approx\left(1-\frac{1}{\left|E\right|}\cdot\frac{\left|E\right|}{2}\right)\left|f\right|=\frac{\left|f\right|}{2}\implies \\ \left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\frac{\left|f\right|}{2} $$ This means that we can improve our flow by as much as $\frac{|f|}{2} $. Why wouldn't answer C be correct?

Answer 1

Let $h(x)=(1-\frac1{x})^{\frac x2}$ for $x\ge2$.
Claim: $h(x)\gt\frac12$ if $x\gt2$.

Proof: Let $g(x)=\ln(1-x)+x$ for $0\le x\lt1$.
Since $g'(x)=-\frac1{1-x} + 1 \le 0$, we have $g(x)\ge g(0)=0$.

$h'(x)=\frac12(1-\frac1{x})^{\frac x2}\left(\ln(1-\frac1x)+\frac{1}{x-1}\right)=\frac12(1-\frac1{x})^{\frac x2}\left(g(\frac1x) + \frac1{x(x-1)}\right)\gt0$ for $x\ge2$.
So $h(x)\gt h(2)=\frac12$ for $x\gt2$. $\quad\checkmark$

---

$$\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\approx\left(1-\frac{1}{\left|E\right|}\cdot\frac{\left|E\right|}{2}\right)\left|f\right|=\frac{\left|f\right|}{2}$$

The above approximation is misleading, as the claim above implies that $\left(1-\frac{1}{\left|E\right|}\right)^{\frac{\left|E\right|}{2}}\left|f\right|\gt\frac{\left|f\right|}2$ when $|E|\gt2$. Hence, it is impossible to obtain $\left|f^{*}\right|-\left|f^{\frac{\left|E\right|}{2}}\right|\le\frac{\left|f\right|}{2}$ from the lemma you learned in the class. So, you should not be able to ascertain answer C is correct.