Lesson 12

Some historical notes. This result is sometimes referred to as the even cycle theorem. Erdős conjectured in 1964 that every \(n\)-vertex graph with no simple cycle of length \(2k\) has at most \(O(n^{1+1/k})\) edges. Bondy and Simonovits proved a strengthened form of this conjecture in 1974.

The bound in Erdős's theorem is tight up to constant factors for the values \(k=2,3,5\): for each of these values, there exist \(n\)-vertex graphs with \(\Omega(n^{1+1/k})\) edges and with no cycle of length \(2k\). For all other values of \(k\), it remains unknown whether there exist \(C_{2k}\)-free graphs with \(\Omega(n^{1+1/k})\) edges, matching the upper bound of Erdős, Bondy, and Simonovits. The best general lower bounds currently known are weaker: \(\Omega(n^{1+2/(3k-3)})\) when \(k\) is odd, and \(\Omega(n^{1+2/(3k-4)})\) when \(k\) is even.