On Arithmetic Progressions of Cycle Lengths in Graphs

A question recently posed by Häggkvist and Scott asked whether or not there exists a constant c such that, if G is a graph of minimum degree ck , then G contains cycles of k consecutive even lengths. In this paper we answer the question by proving that, for k > 2, a bipartite graph of average degree at least 4 k and girth g contains cycles of ( g /2 − 1) k consecutive even lengths. We also obtain a short proof of the theorem of Bondy and Simonovits, that a graph of order n and size at least 8( k − 1) n 1+1/ k has a cycle of length 2 k .