On Erdős Problem 767: Cycles with Chords

Abstract

For integers $k\ge 1$ and $n\ge k+2$, let $g_k(n)$ be the maximum number of edges in an $n$-vertex graph containing no cycle with a vertex incident with at least $k$ chords. Erdős conjectured that $g_k(n)=(k+1)(n-k-1)$ for $n\ge 2k+2$. Lewin found a counterexample. Bollobás later conjectured that there exists a function $n(k)$ such that $g_k(n)=(k+1)(n-k-1)$ for all $n\ge n(k)$. Jiang confirmed this by proving the formula for all $n\ge 3k+3$ when $k\ge 1$. In this paper, we determine $g_k(n)$ completely. For all $k\ge 1$ and $n\ge k+2$, we prove $g_k(n)=\{\lfloor \frac{(k+1)n}{2}\rfloor ,\max \{a(n-a)+\lfloor \frac{a(k+1-a)}{2}\rfloor :a\in \mathbb{Z},\lfloor (k+1)/2\rfloor +1\le a\le k+1\}\}$. For $k\ge 2$, we prove $g_k(n)=(k+1)(n-k-1)$ when $n\ge \lceil (5k+1)/2\rceil$, and this threshold is sharp. Our proof builds on the method developed by Ma and the second author in [Ma and Ning, 2020].

22 pages, 2 figures