Problem Statement
Is it true that for every infinite arithmetic progression $P$ which contains even numbers there is some constant $c=c(P)$ such that every graph with average degree at least $c$ contains a cycle whose length is in $P$?
Categories:
Graph Theory Cycles
Progress
In [Er82e] Erdős credits this conjecture to himself and Burr. This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(P)$ is unknown.See also [72].
Source: erdosproblems.com/71 | Last verified: January 13, 2026