Problem Statement
Does every triangle-free graph on $5n$ vertices contain at most $n^5$ copies of $C_5$?
Categories:
Graph Theory
Progress
Győri proved this with $1.03n^5$, which has been improved by Füredi. The answer is yes, as proved independently by Grzesik [Gr12] and Hatami, Hladky, Král, Norine, and Razborov [HHKNR13].In [Er92b] and [Er97f] Erdős asks more generally: if $r\geq 5$ is odd and a graph has $rn$ vertices and the smallest odd cycle has size $r$ then is the number of cycles of size $r$ at most $n^{r}$?
Source: erdosproblems.com/24 | Last verified: January 13, 2026