Proving existence of $d$-regular subgraph

42 Views Asked by At

Show that for every $\epsilon > 0$, there exists a $\delta = \delta(\epsilon) \geq 0$ and $n_0 = n_0(\epsilon)$ such that every graph $G = (V,E)$ with $n > n_0$ vertices and at least $\epsilon n^2$ edges contains a $d$-regular subgraph, where $d \geq \delta n$.

This problem seems to require the Szemerédi regularity lemma, but I'm not sure how to proceed. Any hints or tips would be greatly appreciated.