Iterative vertex removal algorithm
After removing the first vertex, the new graph has $n' := n-1$ vertices and $m' := m-d_G(u) &gt; m-k$ edges. Therefore
$$
\frac{m'}{n'} &gt; \frac{m-k}{n-1} = k.
$$
Continuing in this way, we see that at any point in time, the ratio between edges and vertices is always at least $k$. Any graph on $\ell$ vertices has a ratio of at most $\binom{\ell}{2}/\ell = \frac{\ell-1}{2}$, so the number of vertices always satisfies $\ell \geq 2k+1$. In other words, when the algorithm terminates, there will be at least $2k+1$ vertices left.