[1] If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity.
A cubic graph (all vertices have degree three) of girth g that is as small as possible is known as a g-cage (or as a (3,g)-cage).
Paul Erdős was the first to prove the general result, using the probabilistic method.
[4] More precisely, he showed that a random graph on n vertices, formed by choosing independently whether to include each edge with probability n(1–g)/g, has, with probability tending to 1 as n goes to infinity, at most n/2 cycles of length g or less, but has no independent set of size n/2k .
The circumference of a graph is the length of the longest (simple) cycle, rather than the shortest.
[6] The girth of an undirected graph can be computed by running a breadth-first search from each node, with complexity