On a conjecture of Bondy and Vince

Abstract

Twenty years ago Bondy and Vince conjectured that for any nonnegative integer $k$, except finitely many counterexamples, every graph with $k$ vertices of degree less than three contains two cycles whose lengths differ by one or two. The case $k\le 2$ was proved by Bondy and Vince, which resolved an earlier conjecture of Erdős et. al.. In this paper we confirm this conjecture for all $k$.

8 pages, updated according to referee reports