The maximum valency of regular graphs with given order and odd girth
Guohui Zhang · Journal of Graph Theory · 1992
Abstract 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 dn, g ≥ 2|n/g≥ if n ≥ 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 ≥ gj, where g ≥ 5 is odd and j ≥ 2. A different variation of the problem is also discussed.