Skip to main content

Section 3.5 Better Bounds for Even Cycles

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].
described in detail following the image
“Breadth-first search.”
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.
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.

Proof.

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.

Proof.

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.

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: