Problem Statement
Let $h(n)$ be minimal such that there is a graph on $n$ vertices with $n+h(n)$ edges which contains a cycle on $k$ vertices, for all $3\leq k\leq n$. Estimate $h(n)$. In particular, is it true that\[h(n) \geq \log_2n+\log_*n-O(1),\]where $\log_*n$ is the iterated logarithmic function?
Categories:
Graph Theory Cycles
Progress
Such graphs are called pancyclic. A problem of Bondy [Bo71], who claimed a proof (without details) of\[\log_2(n-1)-1\leq h(n) \leq \log_2n+\log_*n+O(1).\]Erdős [Er71] believed the upper bound is closer to the truth, but could not even prove $h(n)-\log_2n\to \infty$.A proof of the above lower bound is provided by Griffin [Gr13]. The first published proof of the upper bound appears to be in Chapter 4.5 of George, Khodkar, and Wallis [GKW16].
Source: erdosproblems.com/1016 | Last verified: January 19, 2026