Logo
All Random Solved Random Open
SOLVED
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?
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].

Additional thanks to: Raphael Steiner