Problem 752

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$ ?

Source: erdosproblems.com/752

Graph theory
Cycles

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The theorem of Sudakov and Verstraëte [SuVe08] that gives the answer yes is recorded on the claim page Sudakov and Verstraëte, from which the frontmatter standing is derived; the earlier case $s=2$ , by Erdős, Faudree, Rousseau and Schelp [EFRS99], has its own partial claim page Erdős, Faudree, Rousseau and Schelp.

SuVe08: Sudakov, Benny and Verstraëte, Jacques, Cycle lengths in sparse graphs. Combinatorica 28 (2008), no. 3, 357--372, doi:10.1007/s00493-008-2300-6. Library home: Sudakov and Verstraëte 2008.
EFRS99: Erdős, P., Faudree, R., Rousseau, C. and Schelp, R., The number of cycle lengths in graphs of given minimum degree and girth. Discrete Math. 200 (1999), no. 1--3, 55--60, doi:10.1016/S0012-365X(98)00324-0; reference [11] of [SuVe08]. Not held, and not among the site's reference keys; the site's commentary names Erdős, Faudree and Schelp.

Problem 752

Status

Proof claims

Discussion