Even Circuit Theorem

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

History

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

Lower bounds

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 edges that have no -cycle.

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

for odd values of , or

for even values of .

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^\left(\frac+o(1)\right).$

conjectured that, more generally, the maximum number of edges in a -cycle-free graph is
:$n^\left(\frac+o(1)\right).$.
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^ \le \operatorname(n,C_6) \le 0.6272n^,$
where denotes the maximum number of edges in an -vertex graph that has no subgraph isomorphic to ..
The maximum number of edges in a 10-cycle-free graph can be at least.
:$4\left(\frac\right)^ \approx 0.5798 n^.$

The best proven upper bound on the number of edges, for -cycle-free graphs for arbitrary values of , is
:$n^\left(k-1+o(1)\right).$.

References

{{reflist

Extremal graph theory
Theorems in graph theory