A lower bound on the order of regular graphs with given girth pair

The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209–218]. A (δ, g )‐cage is a smallest δ‐regular graph with girth g . For all δ ≥ 3 and odd girth g  ≥ 5, Harary and Kovács conjectured the existence of a (δ, g )‐cage that contains a cycle of length g  + 1. In the main theorem of this article we present a lower bound on the order of a δ‐regular graph with odd girth g  ≥ 5 and even girth h  ≥  g  + 3. We use this bound to show that every (δ, g )‐cage with δ ≥ 3 and g  ∈ {5,7} contains a cycle of length g  + 1, a result that can be seen as an extension of the aforementioned conjecture by Harary and Kovács for these values of δ, g . Moreover, for every odd g  ≥ 5, we prove that the even girth of all (δ, g )‐cages with δ large enough is at most (3 g  − 3)/2. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 153–163, 2007