PROVED
This has been solved in the affirmative.
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].
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.
View the LaTeX source
This page was last edited 06 October 2025. View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
JoshuaB
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Raphael Steiner
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #767, https://www.erdosproblems.com/767, accessed 2026-04-11
