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.
