In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.^{[1]} If the graph does not contain any cycles (i.e. it's an acyclic graph), its girth is defined to be infinity.^{[2]} For example, a 4cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is trianglefree.
Contents
Cages
A cubic graph (all vertices have degree three) of girth g that is as small as possible is known as a gcage (or as a (3,g)cage). The Petersen graph is the unique 5cage (it is the smallest cubic graph of girth 5), the Heawood graph is the unique 6cage, the McGee graph is the unique 7cage and the Tutte eight cage is the unique 8cage.^{[3]} There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10cages, each with 70 vertices : the Balaban 10cage, the Harries graph and the HarriesWong graph.
The Petersen graph has a girth of 5
The Heawood graph has a girth of 6
The McGee graph has a girth of 7
The Tutte–Coxeter graph (Tutte eight cage) has a girth of 8
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 trianglefree and has chromatic number 4, and repeating the Mycielskian construction used to form the Grötzsch graph produces trianglefree graphs of arbitrarily large chromatic number. 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. 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.
Full article ▸
