A note on two cycles of consecutive even lengths in graphs

Abstract

Bondy and Vince proved that a graph of minimum degree at least three contains two cycles whose lengths differ by one or two, which was conjectured by Erdős. Gao, Li, Ma and Xie gave an average degree counterpart of Bondy-Vince's result, stating that every $n$-vertex graph with at least $\frac{5}{2}(n-1)$ edges contains two cycles of consecutive even lengths, unless $4|(n-1)$ and every block of $G$ is a clique $K_5$. This confirms the case $k=2$ of Verstraëte's conjecture, which states that every $n$-vertex graph without $k$ cycles of consecutive even lengths has edge number $e(G)\le \frac{1}{2}(2k+1)(n-1)$, with equality if and only if every block of $G$ is a clique of order $2k+1$. Sudakov and Verstraëte further conjectured that if $G$ is a graph with maximum number of edges that does not contain $k$ cycles of consecutive even lengths, then every block of $G$ is a clique of order at most $2k+1$. In this paper, we prove the case $k=2$ for Sudakov-Verstraëte's conjecture, by extending the results of Gao, Li, Ma and Xie.

10 pages