DISPROVED (LEAN)
This has been solved in the negative and the proof verified in Lean.
Let $G$ be a graph with chromatic number $\chi(G)=4$. If $m_1<m_2<\cdots$ are the lengths of the cycles in $G$ then can $\min(m_{i+1}-m_i)$ be arbitrarily large? Can this happen if the girth of $G$ is large?
The answer is no: Bondy and Vince
[BoVi98] proved that every graph with minimum degree at least $3$ has two cycles whose lengths differ by at most $2$, and hence the same is true for every graph with chromatic number $4$.
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Raphael Steiner
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #751, https://www.erdosproblems.com/751, accessed 2026-04-11
