HOME

TheInfoList



OR:

In
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 Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol . Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions am ...
. 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 In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
.


Cages

A cubic graph (all vertices have degree three) of girth that is as small as possible is known as a - cage (or as a -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. 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 Petersen graph has a girth of 5 Image:Heawood_Graph.svg, The Heawood graph 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 (''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 at least ; for instance, the Grötzsch graph 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 Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
was the first to prove the general result, using the probabilistic method. 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 graphs of linear groups 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'' 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 In mathematics, systolic geometry is the study of systolic invariants of manifolds and polyhedra, as initially conceived by Charles Loewner and developed by Mikhail Gromov, Michael Freedman, Peter Sarnak, Mikhail Katz, Larry Guth, and o ...
. Girth is the dual concept to
edge connectivity In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration ...
, in the sense that the girth of a
planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
is the edge connectivity of its dual graph, 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, 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