Logo
All Random Solved Random Open
SOLVED
Is it true that for every pair $a,b\geq 1$ such that either $a$ is even or both $a$ and $b$ are odd then there is $c=c(a,b)$ such that every graph with average degree at least $c$ contains a cycle whose length is $\equiv a\pmod{b}$?
This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(a,b)$ is unknown.