The Erdős-Gallai bound for consecutive even cycle lengths
Abstract
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 (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)≥ ((2t+1)(n−1))/2 • either contains t consecutive even cycle lengths, • or equality holds and G is connected with every block isomorphic to K2t+1. As consequences, for every sufficiently large even k we determine the sharp edge thresholds forcing a cycle of length 0pmod k or 2pmod k, answering questions of Bai, Grzesik, Li, and Prorok and of Gao, Li, Ma and Xie, respectively, for sufficiently large even k. The proof develops a stability-enhanced sublinear expander method. Its main new ingredient is a dense-case decomposition that recovers the lengths lost in the expander extraction by combining a flexible dense core with rooted cycle families in the vertices outside the core.
Related
BibTeX
@misc{chen2026erdősgallai,
title = {{The Erdős-Gallai bound for consecutive even cycle lengths}},
author = {Yaobin Chen and Hong Liu and Xia Wang and Xin Wei and Fan Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.27404},
eprint = {2608.27404},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27404},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - The Erdős-Gallai bound for consecutive even cycle lengths
AU - Yaobin Chen
AU - Hong Liu
AU - Xia Wang
AU - Xin Wei
AU - Fan Yang
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2608.27404
UR - https://arxiv.org/abs/2608.27404
AB - 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 (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)≥ ((2t+1)(n−1))/2 • either contains t consecutive even cycle lengths, • or equality holds and G is connected with every block isomorphic to K_2t+1. As consequences, for every sufficiently large even k we determine the sharp edge thresholds forcing a cycle of length 0pmod k or 2pmod k, answering questions of Bai, Grzesik, Li, and Prorok and of Gao, Li, Ma and Xie, respectively, for sufficiently large even k. The proof develops a stability-enhanced sublinear expander method. Its main new ingredient is a dense-case decomposition that recovers the lengths lost in the expander extraction by combining a flexible dense core with rooted cycle families in the vertices outside the core.
ER -