If $G$ has $2n+1$ vertices and $e$ edges, then it contains a bipartite subgraph with at least $e(n+1)/2n+1$ edges.

Question

This theorem is reproduced from Theorem 2.2.2 of The Probabilistic Method 4th edition. Shouldn't the number of edges be at least $e(n+1)/(2n+1)$ instead of $e(n+1)/2n+1$ since any edge has $$\frac{n+1}{2n}\cdot\frac{n}{2n+1}+\frac{n}{2n}\cdot\frac{n+1}{2n+1}=\frac{n+1}{2n+1}$$ of being crossing. I have been trying to see how it should be $e(n+1)/2n+1$ but now I suspect it might be a typo.

Answer 1

It is indeed a typo. To see that such a graph need not contain a bipartite subgraph with at least $e(n+1)/2n + 1$ edges, consider $K_{2n+1}$ and argue that the bipartite subgraph with most edges that it contains is a copy of $K_{n,n+1}$. Then note that $K_{n,n+1}$ has $n(n+1)$ edges but the quantity $e(n+1)/2n + 1$ is $$ \binom{2n+1}{2}(2n+2)/(4n+2) +1 = \frac{(2n)(2n+2)}{4} + 1 = n(n+1) + 1> n(n+1).$$