Even circuit theorem

In extremal graph theory, the even circuit theorem is a result of Paul Erdős according to which an n-vertex graph that does not have a simple cycle of length 2k can only have O(n^{1 + 1/k}) edges. For instance, 4-cycle-free graphs have O(n^3/2) edges, 6-cycle-free graphs have O(n^4/3) edges, etc. The result was stated without proof by Erdős in 1964. Bondy & Simonovits (1974) proved a stronger version of the theorem, according to which, for n-vertex graphs with Ω(n^{1 + 1/k}) edges, all even cycle lengths between 2k and 2kn^1/k occur.

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 Ω(n^{1 + 1/k}) edges that have no 2k-cycle.

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, in this case it is known that the maximum number of edges in a 4-cycle-free graph is

$n^{3/2}\left({\frac {1}{2}}+o(1)\right).$

Erdős & Simonovits (1982) conjecture that, more generally, the maximum number of edges in a 2k-cycle-free graph is

$n^{1+1/k}\left({\frac {1}{2}}+o(1)\right).$

However, the best proven upper bound on this number of edges, for general k, has a larger constant factor: it is

$n^{1+1/k}\left(k-1+o(1)\right).$