A randomized construction of high girth regular graphs

We describe a new random greedy algorithm for generating regular graphs of high girth: Let k  ≥ 3 and c  ∈ (0, 1) be fixed. Let n ∈ ℕ be even and set g = c log k − 1 ( n ) . Begin with a Hamilton cycle G on n vertices. As long as the smallest degree δ ( G ) < k , choose, uniformly at random, two vertices u ,  v  ∈  V ( G ) of degree δ ( G ) whose distance is at least g  − 1. If there are no such vertex pairs, abort. Otherwise, add the edge uv to E ( G ). We show that with high probability this algorithm yields a k ‐regular graph with girth at least g . Our analysis also implies that there areΩ ( n )k n / 2labeled k ‐regular n ‐vertex graphs with girth at least g .