Problem Statement
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$?
Categories:
Graph Theory Cycles
Progress
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$.
Source: erdosproblems.com/752 | Last verified: January 16, 2026