Problem Statement
Let $f(n)$ be the maximal number of edges in a graph on $n$ vertices such that all cycles have more vertices than diagonals. Is it true that $f(n)\ll n$?
Categories:
Graph Theory Cycles
Progress
A problem of Hamburger and Szegedy.Chen, Erdős, and Staton [CES96] proved $f(n) \ll n^{3/2}$. Draganić, Methuku, Munhá Correia, and Sudakov [DMMS24] have improved this to\[f(n) \ll n(\log n)^8.\]
Source: erdosproblems.com/642 | Last verified: January 15, 2026