# Girth (graph theory) > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Girth_(graph_theory) > Markdown URL: https://mediated.wiki/source/Girth_(graph_theory).md > Source: https://en.wikipedia.org/wiki/Girth_(graph_theory) > Source revision: 1263898278 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{short description|Length of a shortest cycle contained in the graph}} In [graph theory](/source/graph_theory), the '''girth''' of an [undirected graph](/source/undirected_graph) is the length of a shortest [cycle](/source/Cycle_(graph_theory)) contained in the graph.R. Diestel, ''Graph Theory'', p.8. 3rd Edition, Springer-Verlag, 2005 If the graph does not contain any cycles (that is, it is a [forest](/source/forest_(graph_theory))), its girth is defined to be [infinity](/source/infinity).{{mathworld|id=Girth|title=Girth|mode=cs2}} 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](/source/triangle-free_graph). ==Cages== {{main|Cage (graph theory)}} A [cubic graph](/source/cubic_graph) (all vertices have degree three) of girth {{mvar|g}} that is as small as possible is known as a {{mvar|g}}-[cage](/source/cage_(graph_theory)) (or as a {{math|(3,''g'')}}-cage). The [Petersen graph](/source/Petersen_graph) is the unique 5-cage (it is the smallest cubic graph of girth 5), the [Heawood graph](/source/Heawood_graph) is the unique 6-cage, the [McGee graph](/source/McGee_graph) is the unique 7-cage and the [Tutte eight cage](/source/Tutte_eight_cage) is the unique 8-cage.{{citation|first=Andries E.|last=Brouwer|author-link=Andries 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). 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](/source/Balaban_10-cage), the [Harries graph](/source/Harries_graph) and the [Harries–Wong graph](/source/Harries%E2%80%93Wong_graph). Image:Petersen1 tiny.svg|The [Petersen graph](/source/Petersen_graph) has a girth of 5 Image:Heawood_Graph.svg|The [Heawood graph](/source/Heawood_graph) has a girth of 6 Image:McGee graph.svg|The [McGee graph](/source/McGee_graph) has a girth of 7 Image:Tutte eight cage.svg|The [Tutte–Coxeter graph](/source/Tutte%E2%80%93Coxeter_graph) (''Tutte eight cage'') has a girth of 8 ==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](/source/chromatic_number) at least {{math|χ}}; for instance, the [Grötzsch graph](/source/Gr%C3%B6tzsch_graph) is triangle-free and has chromatic number 4, and repeating the [Mycielskian](/source/Mycielskian) construction used to form the Grötzsch graph produces triangle-free graphs of arbitrarily large chromatic number. [Paul Erdős](/source/Paul_Erd%C5%91s) was the first to prove the general result, using the [probabilistic method](/source/probabilistic_method).{{citation | last = Erdős | first = Paul | author-link = Paul Erdős | 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 }}. More precisely, he showed that a [random graph](/source/random_graph) on {{mvar|n}} vertices, formed by choosing independently whether to include each edge with probability {{math|''n''(1–''g'')/''g''}}, has, with probability tending to 1 as {{mvar|n}} goes to infinity, at most {{math|{{sfrac|''n''|2}}}} cycles of length {{mvar|g}} or less, but has no [independent set](/source/Independent_set_(graph_theory)) of size {{math|{{sfrac|''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](/source/Cayley_graph)s of [linear group](/source/linear_group)s over [finite field](/source/finite_field)s.{{citation | last1 = Davidoff | first1 = Giuliana | author1-link = Giuliana Davidoff | last2 = Sarnak | first2 = Peter | author2-link = Peter Sarnak | 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}} These remarkable ''[Ramanujan graphs](/source/Ramanujan_graphs)'' also have large [expansion coefficient](/source/expander_graph). == 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](/source/systolic_geometry). Girth is the dual concept to [edge connectivity](/source/k-edge-connected_graph), in the sense that the girth of a [planar graph](/source/planar_graph) is the edge connectivity of its [dual graph](/source/dual_graph), and vice versa. These concepts are unified in [matroid theory](/source/matroid_theory) by the [girth of a matroid](/source/matroid_girth), the size of the smallest dependent set in the matroid. For a [graphic matroid](/source/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 }}. == Computation == The girth of an undirected graph can be computed by running a [breadth-first search](/source/breadth-first_search) from each node, with complexity O(nm) where n is the number of vertices of the graph and m is the number of edges.{{Cite web |url=http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf |title=Question 3: Computing the girth of a graph |access-date=February 22, 2023 |archive-date=August 29, 2017 |archive-url=https://web.archive.org/web/20170829175217/http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf |url-status=dead }} 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.{{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}} Better algorithms are known in the case where the girth is even{{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}} and when the graph is planar.{{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}} In terms of lower bounds, computing the girth of a graph is at least as hard as solving the [triangle finding problem](/source/triangle_finding_problem) on the graph. == References == Category:Graph invariants --- Adapted from the Wikipedia article [Girth (graph theory)](https://en.wikipedia.org/wiki/Girth_(graph_theory)) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Girth_(graph_theory)?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.