Girth (graph theory)

related topics
{math, number, function}
{@card@, make, design}
{village, small, smallsup}

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 4-cycle (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 triangle-free.

Contents

Cages

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). 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, the McGee graph is the unique 7-cage and the Tutte eight cage is the unique 8-cage.[3] There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10-cages, each with 70 vertices : the Balaban 10-cage, the Harries graph and the Harries-Wong 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 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.[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 ▸

related documents
Figure-eight knot (mathematics)
Rectangle
HPGL
Unknot
Linearity of integration
Euler's theorem
List of Fourier-related transforms
Product of group subsets
Z notation
Hilbert's Nullstellensatz
Surjective function
Group object
Online algorithm
Constant folding
The Third Manifesto
Discrete mathematics
De Bruijn-Newman constant
Hurwitz polynomial
Precondition
Sigmoid function
Conjugate closure
Context-free language
Derivative of a constant
Direct sum of groups
Distinct
Essential singularity
Greibach normal form
RC5
CycL
Sierpiński carpet