THE MAXIMUM VALENCY OF REGULAR GRAPHS WITH GIVEN ORDER AND ODD GIRTH

The odd girth of a graph G is the length of a shortest odd cycle in G. Let d(n,g) denote the largest k such that there exists a k-regular graph of order n and odd girth g. It is shown that d(n,g) greater-than-or-equal-to 2 right perpendicular n/g left perpendicular if n greater-than-or-equal-to 2g. As a consequence, we prove a conjecture of Pullman and Wormald, which says that there exists a 2j-regular graph of order n and odd girth g if and only if n greater-than-or-equal-to gj, where g greater-than-or-equal-to 5 is odd and j greater-than-or-equal-to 2. A different variation of the problem is also discussed.