Lesson 11

Now we use the estimate on \(m_{i}\) to prove that the levels grow quickly. We will show by induction that, for every \(i<\ell\), \[\frac{|V_{i+1}|}{|V_i|}>\frac{2\delta}{9\ell}.\]

For \(i=0\), we have \(|V_{0}|=1\) and \(|V_{1}|=\deg(c)>\delta>\frac{2\delta}{9\ell}\), so the inequality is clear.

For the induction step, assume \(i\ge 1\) and that the inequality is already known for \(i-1\). Every edge incident to a vertex of \(V_{i}\) goes either to \(V_{i-1}\) or to \(V_{i+1}\), hence \[\delta |V_{i}| \le m_{i-1}+m_{i} \le 2\ell(|V_{i-1}|+2|V_{i}|+|V_{i+1}|).\] Here the second inequality follows from the estimate on \(m_{i}\) proved above. By the induction hypothesis, \[\frac{|V_{i-1}|}{|V_i|}<\frac{9\ell}{2\delta}.\] Therefore \[\frac{|V_{i+1}|}{|V_i|}> \frac{1}{2\ell}\left(\delta-4\ell-\frac{9\ell^2}{\delta}\right) \ge \frac{\delta-5\ell}{2\ell}\ge \frac{2\delta}{9\ell},\] where we used \(\delta\ge 9\ell\). This proves the expansion estimate \(\frac{|V_{i + 1}|}{|V_i|}> \frac{2 \delta}{9 \ell}\).

Multiplying it for \(i=0,1,\dotsc,\ell-1\), we obtain \[|V_{\ell}| > \left(\frac{2\delta}{9\ell}\right)^{\ell} |V_{0}|.\] But we know that \(\frac{2\delta}{9\ell}\ge n^{1/\ell}\), and \(|V_{0}|=1\). Hence \[|V_{\ell}|> (n^{1/\ell})^{\ell}=n,\] which is impossible because \(G'\) has at most \(n\) vertices. The contradiction shows that \(G'\) contains a cycle of length \(2\ell\), and therefore so does \(G\).