---
tag: D13K9GJT0B
kind: concept
name: Girth
msc: [05C38]
sources:
  - url: https://en.wikipedia.org/wiki/Girth_(graph_theory)
same_as:
  wikidata: Q959831
  wikipedia: Girth (graph theory)
---

## Summary

The girth of a graph is the length of its shortest [[cycle|0Z05VCBQ7Y]], and it is infinite for a graph without cycles.
Large girth means that the graph looks like a tree near each vertex.
Graphs with both large girth and large chromatic number exist, a classical result of the probabilistic method.
The node [[girth|WZ4JGTG6ZD]] gives the precise definition.

## Explanations

### L1 human

Walk around the smallest loop you can find in a graph and count its edges: that number is the girth.
A triangle gives girth $3$, and a graph whose smallest loops are squares has girth $4$, like a grid of streets.
The [[Petersen graph|0NR95CTFCZ]] has girth $5$: it has pentagons but no triangles and no squares.