Problem 72

../

claims/: The 2 claim pages of Problem 72, one per claimant's result; the problem's standing derives from them.

---

Statement. Is there a set $A\subset \mathbb{N}$ of density $0$ and a constant $c>0$ such that every graph on sufficiently many vertices with average degree $\geq c$ contains a cycle whose length is in $A$?

Status. Proved. The claim pages are Verstraëte and Liu and Montgomery, both accepted on refereed publication and the site's credit; the frontmatter standing is derived from them.

Source. erdosproblems.com/72, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #72, https://www.erdosproblems.com/72.

References.

• [Bo77] Bollobás, Béla, Cycles modulo $k$. Bull. London Math. Soc. 9 (1977), no. 1, 97-98.
• [LiMo20] Liu, Hong and Montgomery, Richard, A solution to Erdős and Hajnal's odd cycle problem. arXiv:2010.15802 (2020).
• [Ve05] Verstraete, Jacques, Unavoidable cycle lengths in graphs. J. Graph Theory 49 (2005), no. 2, 151-167. source card (author preprint read; no file held).

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• verstraete_2005_unavoidable_cycle_lengths_graphs
• verstraete_2005_unavoidable_cycle_lengths_graphs / theorem_1
• verstraete_2005_unavoidable_cycle_lengths_graphs / theorem_3_11
• liu_2020_solution_erdos_hajnal_s_odd_cycle
• liu_2020_solution_erdos_hajnal_s_odd_cycle / corollary_1_3