Even circuit theorem

[1] Bondy & Simonovits (1974) published the first proof, and strengthened the theorem to show that, for n-vertex graphs with Ω(n1 + 1/k) edges, all even cycle lengths between 2k and 2kn1/k occur.

[2] The bound of Erdős's theorem is tight up to constant factors for some small values of k: for k = 2, 3, or 5, there exist graphs with Ω(n1 + 1/k) edges that have no 2k-cycle.

[2][3][4] It is unknown for k other than 2, 3, or 5 whether there exist graphs that have no 2k-cycle but have Ω(n1 + 1/k) edges, matching Erdős's upper bound.

[5] Only a weaker bound is known, according to which the number of edges can be Ω(n1 + 2/(3k − 3)) for odd values of k, or Ω(n1 + 2/(3k − 4)) for even values of k.[4] Because a 4-cycle is a complete bipartite graph, the maximum number of edges in a 4-cycle-free graph can be seen as a special case of the Zarankiewicz problem on forbidden complete bipartite graphs, and the even circuit theorem for this case can be seen as a special case of the Kővári–Sós–Turán theorem.

More precisely, the maximum number of edges in a 6-cycle-free graph lies between the bounds where ex(n,G) denotes the maximum number of edges in an n-vertex graph that has no subgraph isomorphic to G.[3] The maximum number of edges in a 10-cycle-free graph can be at least[4] The best proven upper bound on the number of edges, for 2k-cycle-free graphs for arbitrary values of k, is