{"id":"arxiv/2609.15330","url":"https://arxiv.org/abs/2609.15330","tags":["math.CO"],"score":0,"title":"On Erdős Problem 767: Cycles with Chords","domain":"math.CO","source":"arxiv","authors":["Xiaozheng Chen","Bo Ning"],"reviews":0,"subject":"math.CO","summary":"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\\ge3k+3$ when $k\\ge1$. In this paper, we determine $g_k(n)$ completely. For all $k\\ge1$ and $n\\ge k+2$, we prove…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}