Problem 71

Is it true that for every infinite arithmetic progression $P$ which contains even numbers there is some constant $c=c(P)$ such that every graph with average degree at least $c$ contains a cycle whose length is in $P$ ?

Source: erdosproblems.com/71

Graph theory
Cycles

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN). The claim page is Bollobás, accepted on the refereed publication and the site's credit; the frontmatter standing is derived from it. The site's suffix is a catalog label explained under Formalization, and the Current assessment explains how the printed theorem reaches the site's question.

Bo77: Bollobás, Béla, Cycles modulo $k$ . Bull. London Math. Soc. 9 (1977), no. 1, 97-98, doi:10.1112/blms/9.1.97 (received 24 March 1976, revised 9 July 1976; Crossref record). Not held; the publisher's online copy omits the second page, and a scan of both pages is linked from the site's forum thread.
Er82e: Erdős, Paul, Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74, North-Holland (1982), 59-79. Chapter III, §5, printed p. 71, reports the conjecture as proved by Bollobás. Library home: Erdős 1982.

Problem 71

Status

Proof claims

Discussion