Proof of Erdős-Stone Theorem Part II

The following result finishes the guided proof of Erdős-Stone Theorem that started here.

Lemma

Fix $r\in\mathbb{N}$ and $\epsilon>0$. For sufficiently large $n$, starting with any $n$-vertex graph $G$ with at least $(1-1/r+\epsilon)\frac{n^2}{2}$ edges we can keep removing vertex one by one with degree less than $(1-1/r+\epsilon/2)|V(G)|$. When we get stuck, the final graph has $\Theta(n)$ vertices.

Proof

Let $\alpha=1-1/r$. Suppose when we get stuck there are $x$ vertices left. The number of removed edges is less than $(n+(n-1)+\ldots+(x+1))(\alpha+\epsilon/2)$, or $(\alpha+\epsilon/2)\frac{(n+x+1)(n-x)}{2}$. There are at most $\binom{x}{2}$ edges remaining. Hence we have inequality $(\alpha+\epsilon/2)\frac{(n+x+1)(n-x)}{2}+\binom{x}{2}\geq \frac{n^2}{2}(\alpha+\epsilon)$. Thus $\frac{\epsilon}{2}n^2-(\alpha+\epsilon/2)n\leq(1-\alpha-\epsilon/2)x^2$.

$\diamond$