Girth (graph theory)

[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