In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the girth of a graph is the length of a shortest cycle

Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...

 contained in the graph. If the graph does not contain any cycles (i.e. it's an acyclic graph), its girth is defined to be infinity

Infinity

Infinity is a concept in many fields, most predominantly mathematics and physics, that refers to a quantity without bound or end. People have developed various ideas throughout history about the nature of 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

Triangle-free graph

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 girth ≥ 4, graphs with no induced 3-cycle, or locally...

.

Cages

A cubic graph

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....

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

Cage (graph theory)

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an -graph exists...

 (or as a (3,)-cage). The Petersen graph

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 named for Julius Petersen, who in 1898 constructed it...

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

Heawood graph

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.-Combinatorial properties:...

 is the unique 6-cage, the McGee graph

McGee graph

In the mathematical field of graph theory, the McGee Graph or the -cage is a 3-regular graph with 24 vertices and 36 edges.The McGeeGraph is the unique -cage . It is also the smallest cubic cage that is not a Moore graph.First discovered by Sachs but unpublished, the graph is named after McGee who...

 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

Balaban 10-cage

In the mathematical field of graph theory, the Balaban 10-cage or Balaban -cage is a 3-regular graph with 70 vertices and 105 edges named after A. T. Balaban. Published in 1972, It was the first -cage discovered but is not unique....

, the Harries graph

Harries graph

In the mathematical field of graph theory, the Harries graph or Harries -cage is a 3-regular undirected graph with 70 vertices and 105 edges....

 and the Harries-Wong graph.

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

Grötzsch graph

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, and chromatic number 4. It is named after German mathematician Herbert Grötzsch, and its existence demonstrates that the assumption of planarity is necessary in Grötzsch's theorem ...

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

Mycielskian

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ formed from G by a construction of , who used it to show that there exist triangle-free graphs with arbitrarily large chromatic number.-Construction:Let the n vertices of the given...

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

Paul Erdos

Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...

 was the first to prove the general result, using the probabilistic method

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 from a specified class, the probability that the...

. More precisely, he showed that a random graph

Random graph

In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...

 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

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...

 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.

Related concepts

The odd girth and even girth of a graph are the lengths of a shortest odd cycle and shortest even cycle respectively.

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.