Define \(t_r:=t\) and, for \(1\leq s\leq r-1\text{,}\) let \(t_s:=\lceil (2/\varepsilon) t_{s+1}\rceil\text{.}\) What we will prove is that, for all \(1\leq s\leq r\text{,}\) the graph \(G\) contains a complete \(s\)-partite graph in which each part has cardinality at least \(t_s\text{.}\) The result will then follow by setting \(s=r\text{.}\) We proceed by induction on \(s\) where, in the base case \(s=1\text{,}\) we simply select any set of at least \(t_1\approx (2/\varepsilon)^{r-1} t\) vertices in \(G\text{.}\)

Now, for \(s\geq2\text{,}\) let \(B_1,\dots,B_{s-1}\) be the parts of a complete \((s-1)\)-partite graph in \(G\) with parts of size exactly \(t_{s-1}\text{.}\) Define \(B:=\bigcup_{i=1}^{s-1}B_i\) and \(U:=V(G)\setminus B\text{.}\) Define

\begin{equation*}
W:=\left\{u\in U: |N(u)\cap B_i|\geq t_s\text{ for all } 1\leq i\leq s-1\right\}\text{.}
\end{equation*}

We want to prove that the set \(W\) is rather large. The way that we will do this is by “double counting” the non-edges from \(U\) to \(B\text{.}\) First of all, each vertex of \(U\setminus W\) has more than

\begin{equation*}
t_{s-1}-t_s \geq \left(1-\frac{\varepsilon}{2}\right)t_{s-1}
\end{equation*}

non-neighbours in \(B\text{.}\) Thus, the number of non-edges between \(U\) and \(B\) is greater than

\begin{equation*}
|U\setminus W|\left(1-\frac{\varepsilon}{2}\right)t_{s-1}= (|V(G)| - |B| - |W|)\left(1-\frac{\varepsilon}{2}\right)t_{s-1}\text{.}
\end{equation*}

On the other hand, by the minimum degree condition, each vertex in \(B\) is only incident to at most \(\left(\frac{1}{r-1} -\varepsilon\right)(|V(G)|-1)\) non-edges. Thus, the number of non-edges between \(U\) and \(B\) is at most

\begin{equation*}
|B|\left(\frac{1}{r-1} -\varepsilon\right)(|V(G)|-1) \lt t_{s-1}\left(1- \varepsilon(r-1)\right)|V(G)|\text{.}
\end{equation*}

Putting this together, we get

\begin{equation*}
(|V(G)| - |B| - |W|)\left(1-\frac{\varepsilon}{2}\right)t_{s-1} \lt t_{s-1}\left(1- \varepsilon(r-1)\right)|V(G)|
\end{equation*}

which implies that

\begin{equation*}
|W|\left(1-\frac{\varepsilon}{2}\right) > \varepsilon\cdot (r-(3/2))\cdot |V(G)| - (r-1)t_{s-1}\text{.}
\end{equation*}

By letting \(|V(G)|\) be sufficiently large, we get that

\begin{equation*}
|W| > \binom{t_{s-1}}{t_s}^{s-1}(t_s-1)\text{.}
\end{equation*}

The number of ways to choose a set of size \(t_s\) from each of \(B_1,\dots,B_{s-1}\) is precisely \(\binom{t_{s-1}}{t_s}^{s-1}\text{.}\) Thus, by the Pigeonhole Principle, there must be a set \(A\) of \(t_s\) vertices of \(W\) and subsets \(B_i'\) of \(B_i\) for \(1\leq i\leq s-1\) such that every vertex in \(A\) is adjacent to every vertex in \(\bigcup_{i=1}^{s-1}B_i'\text{.}\) This completes the proof.