Girth (graph theory)

In graph theory, girth is a special idea that helps us understand how graphs are put together. It tells us the length of the smallest loop, or cycle, in a graph. For example, if you imagine a square made of lines connecting four points, the girth would be 4 because that’s the fewest lines you need to make a loop.

If a graph doesn’t have any loops at all—like a tree with branches that never meet—it is called a forest, and its girth is said to be infinity. This means there is no smallest loop because there are no loops.

Girth is important because it helps mathematicians study the shape and connections in graphs. For instance, a triangular mesh—like the pattern on a soccer ball—has a girth of 3 because its smallest loop uses three lines. Graphs with larger girths, like 4 or more, are special because they don’t contain any triangles, making them triangle-free.

Cages

Main article: Cage (graph theory)

In graph theory, a special type of graph called a g-cage is the smallest possible cubic graph — where each point, or vertex, connects to exactly three other points — that has a specific girth g. The girth is the length of the shortest loop in the graph. For example, the Petersen graph is the smallest cubic graph with a girth of 5, meaning the shortest loop in it has 5 edges. Similarly, the Heawood graph has a girth of 6, the McGee graph has a girth of 7, and the Tutte–Coxeter graph (also called the Tutte eight cage) has a girth of 8. For some girths, there might be more than one smallest graph, such as three different graphs that each have a girth of 10.

Girth and graph coloring

In graph theory, you can find graphs that have both a long distance between repeating paths and need many colors to color them without neighboring points sharing the same color. For example, the Grötzsch graph has no small repeating paths but still needs four colors.

Famous mathematician Paul Erdős showed this is possible using a clever method with chance. He also discovered special graphs made from patterns in numbers that have these interesting properties too.

Related concepts

The odd girth and even girth of a graph refer to the lengths of the shortest odd cycle and shortest even cycle in the graph, respectively. The circumference of a graph is the length of the longest cycle, not the shortest.

Girth is connected to other ideas in mathematics, such as edge connectivity in planar graphs. These ideas come together in matroid theory.

Computation

To find the girth of a graph, you can use a method called breadth-first search starting from each node. This process can take some time, depending on how many nodes (points) and edges (lines connecting points) the graph has. There are smarter ways to do this, like stopping the search once you find a small cycle. Special tricks make it easier for certain types of graphs, like those that are flat or have only even-length cycles. Figuring out the girth is also at least as tricky as finding whether three nodes form a triangle in the graph.

Main article: Triangle finding problem