### Theorem 3.5.1. Bondy and Simonovits [42].

For \(k\geq2\text{,}\)

\begin{equation*}
\ex(n,C_{2k}) = O\left(n^{1+\frac{1}{k}}\right)
\end{equation*}

where the constant factor depends on \(k\text{.}\)

In the previous section, we proved an upper bound which holds for any bipartite graph. In this section, we consider the special case of even cycles \(C_{2k}\) for \(k\geq2\text{.}\) In this case, since cycles are rather sparse (and, therefore, are easier to find in a graph), we expect the upper bounds to be much lower than for complete bipartite graphs. The following result was originally proved by Bondy and Simonovits [42].

“Breadth-first search.”

For \(k\geq2\text{,}\)

\begin{equation*}
\ex(n,C_{2k}) = O\left(n^{1+\frac{1}{k}}\right)
\end{equation*}

where the constant factor depends on \(k\text{.}\)

The proof of this theorem is completely elementary, but is perhaps a bit long and involved. Therefore, for the purposes of these notes, we will prove a weaker variant of it. Given an integer \(n\) and set \(\mathcal{H}\) of graphs, let ex(n,calH) be the maximum number of edges in a graph on \(n\) vertices which does not contain a copy of any graph \(H\in\mathcal{H}\text{.}\) We prove the following.

For any \(k\geq2\) and \(n\geq1\text{,}\)

\begin{equation*}
\ex(n,\{C_4,C_6,\dots,C_{2k}\}) \leq 2n\left(n^{1/k}+1\right)\text{.}
\end{equation*}

As a first step in the proof of Theorem 3.5.2, we will “throw away” a bunch of the graph \(G\) to obtain a bipartite graph with large minimum degree; the utility of this will be seen later on. The next two lemmas are useful for doing this.

Every graph \(G\) has a bipartite subgraph with \(|V(G)|\) vertices and at least \(|E(G)|/2\) edges.

Let \(A\) be a subset of \(V(G)\) obtained by including each vertex of \(G\) in \(A\) with probability \(1/2\text{,}\) independently of one another, and then delete all edges with both endpoints in \(A\) or both endpoints in \(V(G)\setminus A\text{.}\) This procedure always produces a bipartite subgraph of \(G\text{.}\) For each edge \(uv\) of \(G\text{,}\) the probability that \(uv\) survives this procedure is

\begin{equation*}
\mathbb{P}(u\in A\text{ and } v\in V(G)\setminus A) + \mathbb{P}(u\in V(G)\setminus A\text{ and } v\in A) = \frac{1}{2}\text{.}
\end{equation*}

Therefore, the expected number of edges in the random bipartite subgraph produced is \(|E(G)|/2\text{,}\) and so there must be a bipartite subgraph of \(G\) with at least this many edges.

Every graph \(G\) has a subgraph of minimum degree at least \(|E(G)|/|V(G)|\text{.}\)

The proof is similar to that of Lemma 3.3.12, but the analysis is simpler. We proceed by induction on \(|V(G)|\text{,}\) where the case \(|V(G)|=1\) is trivial. Now, for \(|V(G)|\geq2\text{,}\) let \(x\) be a vertex of minimum degree in \(G\text{.}\) If its degree is at least \(|E(G)|/|V(G)|\text{,}\) then we are done. So, suppose that it is less than this and let \(G':=G-x\text{.}\)

By induction, there is a subgraph \(G''\) of \(G'\) with minimum degree at least \(|E(G')|/|V(G')|\text{.}\) To complete the proof, all we need to do is to show that \(|E(G')|/|V(G')|\geq |E(G)|/|V(G)|\text{.}\) Indeed, we have

\begin{equation*}
\frac{|E(G')|}{|V(G')|} = \frac{|E(G)|-d(x)}{|V(G)|-1}>\frac{|E(G)|-|E(G)|/|V(G)|}{|V(G)|-1}=\frac{|E(G)|}{|V(G)|}
\end{equation*}

and so we are done.

We present a proof of Theorem 3.5.2.

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.

Here is a YouTube video related to the extremal number of even cycles: