PROVED
This has been solved in the affirmative.
Let $G$ be a graph with minimum degree $k$ and girth $>2s$ (i.e. $G$ contains no cycles of length $\leq 2s$). Must there be $\gg k^s$ many distinct cycle lengths in $G$?
A question of Erdős, Faudree, and Schelp, who proved it when $s=2$.
The answer is yes, proved by Sudakov and Verstraëte
[SuVe08], who in fact proved that under the assumption of average degree $k$ and girth $>2s$ there are at least $\gg k^s$ many consecutive even integers which are cycle lengths in $G$.
View the LaTeX source
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 #752, https://www.erdosproblems.com/752, accessed 2026-01-16
