View source for Girth (graph theory)

{{short description|Length of a shortest cycle contained in the graph}}
In [[Graph theory|graph theory]], the '''girth''' of an undirected graph is the length of a shortest [[Cycle (graph theory)|cycle]] contained in the graph.<ref>R. Diestel, ''Graph Theory'', p.8.  3rd Edition, Springer-Verlag, 2005</ref> If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be [[Infinity|infinity]].<ref>{{mathworld|id=Girth|title=Girth|mode=cs2}}</ref>
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 graph|triangle-free]].

==Cages==
{{main|Cage (graph theory)}}
A [[Cubic graph|cubic graph]] (all vertices have degree three) of girth {{mvar|g}} that is as small as possible is known as a {{mvar|g}}-[[Cage (graph theory)|cage]] (or as a {{math|(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.<ref>{{citation|first=Andries E.|last=Brouwer|url=http://www.win.tue.nl/~aeb/drg/graphs/|title=Cages}}. Electronic supplement to the book ''Distance-Regular Graphs'' (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).</ref> 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]].

<gallery>
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
</gallery>

==Girth and graph coloring==
For any positive integers {{mvar|g}} and {{math|χ}}, there exists a graph with girth at least {{mvar|g}} and [[Chromatic number|chromatic number]] at least {{math|χ}}; 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. [[Biography:Paul Erdős|Paul Erdős]] was the first to prove the general result, using the [[Probabilistic method|probabilistic method]].<ref>{{citation | last = Erdős | first = Paul |  journal = Canadian Journal of Mathematics | pages = 34–38 | title = Graph theory and probability | volume = 11 | year = 1959 | doi = 10.4153/CJM-1959-003-9| s2cid = 122784453 | doi-access = free }}.</ref> More precisely, he showed that a [[Random graph|random graph]] on {{mvar|n}} vertices, formed by choosing independently whether to include each edge with probability {{math|''n''<sup>(1–''g'')/''g''</sup>}}, has, with probability tending to 1 as {{mvar|n}} goes to infinity, at most {{math|{{frac|''n''|2}}}} cycles of length {{mvar|g}} or less, but has no [[Independent set (graph theory)|independent set]] of size {{math|{{frac|''n''|2''k'' }}}}. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than {{mvar|g}}, in which each color class of a coloring must be small and which therefore requires at least {{mvar|k}} colors in any coloring.

Explicit, though large, graphs with high girth and chromatic number can be constructed as certain [[Cayley graph]]s of [[Linear group|linear group]]s over [[Finite field|finite field]]s.<ref>{{citation | last1 = Davidoff | first1 = Giuliana |  last2 = Sarnak | first2 = Peter |  last3 = Valette | first3 = Alain | doi = 10.1017/CBO9780511615825 | isbn = 0-521-82426-5 | mr = 1989434 | publisher = Cambridge University Press, Cambridge | series = London Mathematical Society Student Texts | title = Elementary number theory, group theory, and Ramanujan graphs |title-link=Elementary Number Theory, Group Theory and Ramanujan Graphs| volume = 55 | year = 2003}}</ref> These remarkable ''Ramanujan graphs'' also have large [[Expander graph|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 '''{{visible anchor|circumference}}''' 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|systolic geometry]].

Girth is the dual concept to [[K-edge-connected graph|edge connectivity]], in the sense that the girth of a [[Planar graph|planar graph]] is the edge connectivity of its [[Dual graph|dual graph]], and vice versa. These concepts are unified in matroid theory by the [[Matroid girth|girth of a matroid]], the size of the smallest dependent set in the matroid. For a [[Graphic matroid|graphic matroid]], the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity.<ref>{{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
 }}.</ref>

== Computation ==

The girth of an undirected graph can be computed by running a [[Breadth-first search|breadth-first search]] from each node, with complexity <math>O(nm)</math> where <math>n</math> is the number of vertices of the graph and <math>m</math> is the number of edges.<ref>[http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf Question 3: Computing the girth of a graph] {{webarchive|url=https://web.archive.org/web/20170829175217if_/http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf|date=August 29, 2017}}</ref> A practical optimization is to limit the depth of the BFS to a depth that depends on the length of the smallest cycle discovered so far.<ref>{{Cite web |last=Völkel |first=Christoph Dürr, Louis Abraham and Finn |date=2016-11-06 |title=Shortest cycle |url=https://tryalgo.org/en/cycles/2016/11/06/shortest-cycle/ |access-date=2023-02-22 |website=TryAlgo |language=en-US}}</ref> Better algorithms are known in the case where the girth is even<ref>{{Cite web |title=ds.algorithms - Optimal algorithm for finding the girth of a sparse graph? |url=https://cstheory.stackexchange.com/questions/10983/optimal-algorithm-for-finding-the-girth-of-a-sparse-graph |access-date=2023-02-22 |website=Theoretical Computer Science Stack Exchange |language=en}}</ref> and when the graph is planar.<ref>{{Cite journal |last1=Chang |first1=Hsien-Chih |last2=Lu |first2=Hsueh-I. |date=2013 |title=Computing the Girth of a Planar Graph in Linear Time |journal=SIAM Journal on Computing |volume=42 |issue=3 |pages=1077–1094 |doi=10.1137/110832033 |arxiv=1104.4892 |s2cid=2493979 |issn=0097-5397}}</ref> In terms of lower bounds, computing the girth of a graph is at least as hard as solving the triangle finding problem on the graph.

== References ==
<references/>

[[Category:Graph invariants]]

{{Sourceattribution|Girth (graph theory)}}