In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth ≥ 4 is triangle-free.

## Cages

A

cubic graph of girth

$g$ that is as small as possible is known as a

$g$-

cage. The

Petersen graph is the unique 5-cage (it is the smallest cubic graph of girth 5), the

Heawood graph is the unique 6-cage, and the

Tutte eight cage is the unique 8-cage.

## Girth and graph coloring

For any positive integers

g and χ, there exists a graph with girth at least

g and

chromatic number at least χ; for instance, the

Grötzsch graph is triangle-free and has chromatic number 4, and repeating the

Mycielskian construction used to form the Grötzsch graph produces triangle-free graphs of arbitrarily large chromatic number.

Paul Erdős was the first to prove the general result, using the

probabilistic method. 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/2

k. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than

g, in which each color class of a coloring must be small and which therefore requires at least

k colors in any coloring.

## See also

## References