Problem 1016

Erdős Problem #1016: declared status 'open'. Formalized: no. 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? Current best: 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\H{o}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]. Prize: no. OEIS: A105206. Tags: cycles, graph theory.