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.
The result was stated without proof by Erdős in 1964.[1] published the first proof, and strengthened the theorem to show that, for -vertex graphs with edges, all even cycle lengths between and 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 edges that have no -cycle.[2]
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 befor odd values of, orfor even values of .
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
n3/2\left(
| 1 | |
| 2 |
+o(1)\right).
conjectured that, more generally, the maximum number of edges in a -cycle-free graph is
n1+1/k\left(
| 1 | |
| 2 |
+o(1)\right).
0.5338n4/3\le\operatorname{ex}(n,C6)\le0.6272n4/3,
| 4\left( | n |
| 5 |
\right)6/5 ≈ 0.5798n6/5.
The best proven upper bound on the number of edges, for -cycle-free graphs for arbitrary values of, is
n1+1/k\left(k-1+o(1)\right).