Let
\(G\) be a graph with
\(n\) vertices and at least
\(2n(n^{1/k}+1)\) edges and suppose, to the contrary, that
\(G\) has no cycle of length
\(\{4,6,\dots,2k\}\text{.}\) Using
Lemma 3.5.3 and
Lemma 3.5.4 (in that order), we get a bipartite subgraph
\(G'\) of
\(G\) such that
\begin{equation*}
\delta(G')\geq \frac{|E(G)|}{2|V(G)|} \geq n^{1/k}+1\text{.}
\end{equation*}
Now, we do a simple “breadth-first search” argument. Let \(v_0\) be any vertex of \(G'\) and, for \(i\geq0\text{,}\) let \(L_i\) be the set of vertices at distance exactly \(i\) from \(v_0\) in \(G'\text{.}\) That is,
\begin{equation*}
L_0=\{v_0\}\text{,}
\end{equation*}
\begin{equation*}
L_1=N_{G'}(v_0)\text{,}
\end{equation*}
\begin{equation*}
L_2=\bigcup_{u\in L_1}N_{G'}(u)\setminus L_0\text{,}
\end{equation*}
and so on. Since \(G'\) is bipartite, there are no edges within any of the sets \(L_i\text{.}\) Also, for \(i\leq k-1\text{,}\) if there are distinct vertices \(u\) and \(v\) in \(L_i\) which have a common neighbour \(w\) in \(L_{i+1}\text{,}\) then, by following the paths form \(u\) and \(v\) back to \(v_0\) which travel through \(L_{i-1},L_{i-2},\dots, L_0\text{,}\) we eventually reach a common “ancestor” of \(u\) and \(v\text{.}\) However, this gives us an even cycle of length at most \(2k\) in \(G'\text{,}\) which is a contradiction. Thus, for \(i\leq k-1\text{,}\) no two vertices of \(L_i\) have a common neighbour in \(L_{i+1}\text{.}\) Thus, each vertex in \(L_{i+1}\) has a unique neighbour in \(L_i\text{.}\) From this, we get that
\begin{equation*}
|L_0|=1\text{,}
\end{equation*}
\begin{equation*}
|L_1|\geq n^{1/k} + 1
\end{equation*}
and, for \(2\leq i\leq k\text{,}\)
\begin{equation*}
|L_i|\geq |L_{i-1}|n^{1/k}\text{.}
\end{equation*}
However, this tells us that \(|L_k|\geq \left(n^{1/k}\right)^{k-1}\left(n^{1/k}+1\right) > n\) which is a contradiction.