graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the girth of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a

forest A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...

), 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 four or more is triangle-free.

Cages

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bi ...

(all vertices have degree three) of girth that is as small as possible is known as a -

cage A cage is an enclosure often made of mesh, bars, or wires, used to confine, contain or protect something or someone. A cage can serve many purposes, including keeping an animal or person in captivity, capturing an animal or person, and displayin ...

(or as a -cage). The

Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...

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

Heawood graph Heawood is a surname. Notable people with the surname include: * Jonathan Heawood, British journalist *Percy John Heawood (1861–1955), British mathematician **Heawood conjecture ** Heawood graph **Heawood number In mathematics, the Heawood numbe ...

is the unique 6-cage, the McGee graph is the unique 7-cage and the Tutte eight cage is the unique 8-cage. 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. Image:Petersen1 tiny.svg, The

has a girth of 5 Image:Heawood_Graph.svg, The

has a girth of 6 Image:McGee graph.svg, The McGee graph has a girth of 7 Image:Tutte eight cage.svg, The

Tutte–Coxeter graph In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph ...

(''Tutte eight cage'') has a girth of 8

Girth and graph coloring

For any positive integers and , there exists a graph with girth at least and

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

at least ; for instance, the

Grötzsch graph In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example ...

is triangle-free and has chromatic number 4, and repeating the

Mycielskian In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic ...

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 The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects fr ...

. More precisely, he showed that a

random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...

on vertices, formed by choosing independently whether to include each edge with probability , has, with probability tending to 1 as goes to infinity, at most cycles of length or less, but has no independent set of size . Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than , in which each color class of a coloring must be small and which therefore requires at least colors in any coloring. Explicit, though large, graphs with high girth and chromatic number can be constructed as certain

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

s of

linear group In mathematics, a matrix group is a group ''G'' consisting of invertible matrices over a specified field ''K'', with the operation of matrix multiplication. A linear group is a group that is isomorphic to a matrix group (that is, admitting a f ...

s over

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...

s. These remarkable ''

Ramanujan graphs In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders. AMurty's survey papernotes, Ram ...

'' also have large expansion coefficient.

Related concepts

The odd girth and even girth of a graph are the lengths of a shortest odd cycle and shortest even cycle respectively. The of a graph is the length of the ''longest'' (simple) cycle, rather than the shortest. Thought of as the least length of a non-trivial cycle, the girth admits natural generalisations as the 1-systole or higher systoles in systolic geometry. Girth is the dual concept to edge connectivity, in the sense that the girth of a planar graph is the edge connectivity of its

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-lo ...

, and vice versa. These concepts are unified in

matroid theory In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

by the girth of a matroid, the size of the smallest dependent set in the matroid. For a

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called ...

, the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity.{{citation , last1 = Cho , first1 = Jung Jin , last2 = Chen , first2 = Yong , last3 = Ding , first3 = Yu , doi = 10.1016/j.dam.2007.06.015 , issue = 18 , journal = Discrete Applied Mathematics , mr = 2365057 , pages = 2456–2470 , title = On the (co)girth of a connected matroid , volume = 155 , year = 2007, doi-access = free .

References

Graph invariants