---

Claim. There is a set $S\subset\mathbb{N}$ with $|S\cap\{1,2,\dots,n\}|=O(n^{0.99})$, hence of density zero, such that every graph with average degree at least $10$ contains a cycle whose length lies in $S$. This is Theorem 1 of J. Verstraëte, Unavoidable cycle lengths in graphs, J. Graph Theory 49 (2005), no. 2, 151--167, published online 2005-03-21. The theorem puts no condition on the number of vertices, so it answers the question of Problem 72 as the page states it, with $A=S$ and $c=10$. The proof shows that such a set exists without exhibiting one.

Acceptance. The paper is a refereed publication in the Journal of Graph Theory, and the site's curator, Thomas Bloom, records the problem as solved by it and labels the problem proved, which is the reviewed evidence listed. The author's undated preprint is the edition described on its source card; the basis here is the statement of Theorem 1 on its p. 1 alone, not the proof on pp. 2--16, and the journal text was not compared. The acceptance recorded here therefore rests on the publication and the site's acceptance, not on a local review.

Later work. Liu and Montgomery proved the same conclusion with an explicit set, the powers of two from some point on, which Erdős had expected to be avoidable. The Lean formalization of a solution to the problem in Boris Alexeev's repository, linked from that page, names this paper among its informal sources but proves the statement through Liu and Montgomery's set.