A High Girth Graph Construction
L. Sunil Chandran · SIAM Journal on Discrete Mathematics · 2003
We give a deterministic algorithm that constructs a graph of girth log k (n) + O(1) and minimum degree k-1, taking number of nodes n and number of edges $e = {\left \lfloor nk / 2 \right \rfloor }$ (where $k < \frac {n}{3}$) as input. The degree of each node is guaranteed to be k-1, k, or k+1, where k is the average degree. Although constructions that achieve higher values of girth---up to $\frac {4}{3} \log_{k-1}{(n)}$---with the same number of edges are known, the proof of our construction uses only very simple counting arguments in comparison. Our method is very simple and perhaps the most intuitive: We start with an initially empty graph and keep introducing edges one by one, connecting vertices which are at large distances in the current graph. In comparison with the Erdös--Sachs proof, ours is slightly simpler while the value it achieves is slightly lower. Also, our algorithm works for all values of n and $k < \frac {n}{3}$, unlike most of the earlier constructions.