Problem Statement
Let $g_k(n)$ be the maximal number of edges possible on a graph with $n$ vertices which does not contain a cycle with $k$ chords incident to a vertex on the cycle. Is it true that\[g_k(n)=(k+1)n-(k+1)^2\]for $n$ sufficiently large?
Categories:
Graph Theory Turan Number
Progress
Czipszer proved that $g_k(n)$ exists for all $k$, and in fact $g_k(n)\leq (k+1)n$. Erdős wrote it is 'easy to see' that\[g_k(n)\geq (k+1)n-(k+1)^2.\]Pósa proved that $g_1(n)=2n-4$ for $n\geq 4$. Erdős could prove the conjectured equality for $n\geq 2k+2$ when $k=2$ or $k=3$.The conjectured equality was proved for $n\geq 3k+3$ by Jiang [Ji04].
Curiously, in [Er69b] Erdős mentions this problem, but states that his conjectured equality for $g_k(n)$ was disproved (for general $k$) by Lewin, citing oral communication. Perhaps Lewin only disproved this for small $n$, or perhaps Lewin's disproof was simply incorrect.
Source: erdosproblems.com/767 | Last verified: January 16, 2026