The Erdős-Gallai bound for consecutive even cycle lengths
Erdős and Gallai in 1959 proved the seminal result that every $n$-vertex graph with no cycle of length at least $2t+2$ has at most $\tfrac{2t+1}{2}(n-1)$ edges. We prove the extension that, for every sufficiently large $t$, the same quantity is also the sharp extremal bound for graphs with no $t$ consecutive even cycle lengths, resolving a conjecture of Verstraëte. Thus, at the Erdős-Gallai threshold, forcing an entire interval of even cycle lengths costs no more than forcing its longest member. More precisely, every $n$-vertex graph $G$ with $e(G)\ge \tfrac{(2t+1)(n-1)}2$ $\bullet$ either…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27404
curl -X POST /api/v1/records/arxiv/2608.27404/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27404/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'