Erdős Problem #642 — Graphs with fewer chords than cycle lengths
For a positive integer , let range over finite simple graphs with . For a simple cycle in , a chord is an edge of joining two vertices of that are not consecutive along ; write for the number of such edges. Define
Is ? Equivalently, do there exist an absolute constant and an integer such that for all ? Erdős Problem #642
Background
The problem is attributed to Hamburger and Szegedy and was recorded by Erdős. It asks for the edge-density threshold that forces a cycle with at least as many chords as vertices, the exact obstruction excluded in the definition of . In related work, Bollobás showed that sufficiently large constant average degree forces a cycle whose chords contain a cycle; Chen, Erdős, and Staton extended this to arbitrarily long chains of cycles, each formed from chords of the preceding one. These nested-cycle results provide context, but they address a different forcing condition. Erdős Problem #642 Cycles with many chords Chen, Erdős, and Staton (1996)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.