Even circuit theorem

In extremal graph theory, the even circuit theorem is a result of Paul Erdős according to which an Template:Mvar-vertex graph that does not have a simple cycle of length Template:Math can only have Template:Math edges. For instance, 4-cycle-free graphs have Template:Math edges, 6-cycle-free graphs have Template:Math edges, etc.

The highest amount of edges for 7 vertices banning 4 and 6 cycles respectively

History

The result was stated without proof by Erdős in 1964. Template:Harvtxt published the first proof, and strengthened the theorem to show that, for Template:Mvar-vertex graphs with Template:Math edges, all even cycle lengths between Template:Math and Template:Math occur.

Lower bounds

Template:Unsolved 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 Template:Math edges that have no Template:Math-cycle.

It is unknown for Template:Mvar other than 2, 3, or 5 whether there exist graphs that have no Template:Math-cycle but have Template:Math edges, matching Erdős's upper bound. Only a weaker bound is known, according to which the number of edges can be Template:Math for odd values of Template:Mvar, or Template:Math for even values of Template:Mvar.

Constant factors

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}(\frac{1}{2}+o(1)).$

Template:Harvtxt conjectured that, more generally, the maximum number of edges in a Template:Math-cycle-free graph is

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

However, later researchers found that there exist 6-cycle-free graphs and 10-cycle-free graphs with a number of edges that is larger by a constant factor than this conjectured bound, disproving the conjecture. More precisely, the maximum number of edges in a 6-cycle-free graph lies between the bounds

$0.5338n^{4/3}\le \mathrm{ex}(n,C_6)\le 0.6272n^{4/3},$

where Template:Math denotes the maximum number of edges in an Template:Mvar-vertex graph that has no subgraph isomorphic to Template:Mvar. The maximum number of edges in a 10-cycle-free graph can be at least

$4{\left(\frac{n}{5}\right)}^{6/5}\approx 0.5798n^{6/5}.$

The best proven upper bound on the number of edges, for Template:Math-cycle-free graphs for arbitrary values of Template:Mvar, is

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