Erdős Problem #752 — Many distinct cycle lengths from minimum degree and girth
For a finite graph , let be its minimum degree, let be the length of its shortest cycle (taken to be if it has no cycles), and define its cycle-length set by
The question is: for every integer , does there exist a constant such that, for every integer and every finite graph satisfying and , one has
The restriction makes explicit the intended degree range: if , a single edge has minimum degree , infinite girth, and no cycle lengths. Erdős Problem #752
Background
The question is recorded among Erdős’s problems on cycle lengths and is attributed to Erdős, Faudree, and Schelp; the case was proved earlier. Its central tension is that forbidding all cycles of length at most imposes strong local sparsity, while a large minimum degree should force a broad range of longer cycle lengths. The result for general is stronger than merely counting distinct lengths: it produces a run of consecutive even cycle lengths. Erdős Problem #752 Erdős (1992)
References
P. Erdős, Some of my favourite problems in various branches of combinatorics, Le Matematiche 47 (1992), no. 2, 231–240.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.