Lesson 8

We now prove the Bondy–Simonovits theorem. Fix \(\ell\) with \(k\le \ell\le k n^{1/k}\). By the bipartite-subgraph lemma, \(G\) contains a bipartite subgraph \(G^{*}\) with \[e(G^{*})>\frac{18k n^{1+1/k}}{2}=9k n^{1+1/k}.\] Set \[\delta=9k n^{1/k}.\] Then, the pruning lemma gives a subgraph \(G'\) of \(G^{*}\) with minimum degree greater than \(\delta\). We take one connected component of this subgraph and call it \(G'\) again. It is enough to find a cycle of length \(2\ell\) in \(G'\).

At first, notice that \(\delta \ge 9 \ell\). Then, we want to show the following \[\delta\ge \frac{9}{2}\ell\cdot n^{1/\ell}.\] So, it is enough to show that \[2k n^{1/k}\ge \ell n^{1/\ell}.\] Consider \(f(x)=x n^{1/x}\) on the interval \([k, k n^{1/k}]\). This function has only one extremum on the positive axis, and it is a minimum. Therefore it is enough to check the endpoints. At \(x=k\) the inequality is immediate. At \(x=k n^{1/k}\) it becomes \[n^{1/(k n^{1/k})}<2,\] which follows from the fact that the maximum of \(y^{1/y}\) over \(y>0\) is \(e^{1/e}<2\).