Girth (graph theory)

In graph theory, girth is an idea that helps us learn about how graphs are built. It tells us the length of the smallest loop, or cycle, in a graph. For example, think of a square made of lines joining four points. The girth would be 4 because that is the fewest lines you need to make a loop.

If a graph has no 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 g-cage is a special type of graph. It is the smallest cubic graph where each point connects to exactly three other points. 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. The Heawood graph has a girth of 6. The McGee graph has a girth of 7. The Tutte–Coxeter graph (also called the Tutte eight cage) has a girth of 8. For some girths, there can be more than one smallest graph. There are three different graphs that each have a girth of 10.

Girth and graph coloring

In graph theory, some graphs have long distances between repeating paths and need many colors to color them so that no neighboring points share 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 special method with chance. He also found special graphs made from number patterns that have these interesting properties too.

Related concepts

The odd girth and even girth of a graph are the lengths of the shortest odd cycle and shortest even cycle in the graph. The circumference of a graph is the length of the longest cycle.

Girth is related to other math ideas, such as edge connectivity in planar graphs. These ideas are part of matroid theory.

Computation

To find the girth of a graph, you can use a method called breadth-first search starting from each node. This can take time, depending on how many nodes and edges the graph has. There are easier ways, like stopping the search when you find a small cycle. Special tricks help for certain types of graphs. Figuring out the girth is also tricky, like finding whether three nodes form a triangle.

Main article: Triangle finding problem