Girth (graph theory) facts for kids

In graph theory, the girth of a graph is the length of the shortest cycle (a path that starts and ends at the same point) found in the graph. Imagine a map with cities and roads; a cycle would be a trip that brings you back to your starting city. The girth is the shortest such trip.

If a graph doesn't have any cycles at all (it's like a forest where all paths are straight or branching, but never loop back), its girth is considered to be infinity.

For example, a square shape is a cycle of length 4, so its girth is 4. A grid pattern also has a girth of 4. A triangular pattern has a girth of 3 because the shortest cycle is a triangle. If a graph has a girth of four or more, it means it doesn't contain any triangles.

Girth and Cages

Imagine a special type of graph where every point (called a vertex) is connected to exactly three other points. This is called a cubic graph. A cage is the smallest possible cubic graph that has a specific girth.

For example, the Petersen graph is the smallest cubic graph with a girth of 5. It's called the unique 5-cage. The Heawood graph is the unique 6-cage, and the McGee graph is the unique 7-cage. The Tutte eight cage is the unique 8-cage.

Sometimes, there can be more than one cage for a certain girth. For instance, there are three different 10-cages, each with 70 points: the Balaban 10-cage, the Harries graph, and the Harries–Wong graph.

• 

  The Petersen graph has a girth of 5

• 

  The Heawood graph has a girth of 6

• 

  The McGee graph has a girth of 7

• 

  The Tutte–Coxeter graph (Tutte eight cage) has a girth of 8

Girth and Graph Coloring

Graph coloring is about assigning colors to the points of a graph so that no two connected points have the same color. The smallest number of colors needed is called the chromatic number.

It's possible for a graph to have a very high girth (meaning no short cycles) but still need many different colors to color it. This might seem surprising! For example, some graphs don't have any triangles (girth of 4 or more) but still need four or more colors.

Mathematicians like Paul Erdős have shown that you can always find graphs that have both a high girth and need many colors. This means that even if a graph doesn't have simple, short loops, it can still be quite complex in how its points are connected.

Other Cycle Lengths

Besides the shortest cycle, we can also talk about other cycle lengths:

• The odd girth is the length of the shortest cycle that has an odd number of points.
• The even girth is the length of the shortest cycle that has an even number of points.

The circumference of a graph is the length of the longest simple cycle in the graph. So, girth is about the shortest loop, and circumference is about the longest loop.

Finding the Girth

Computers can figure out the girth of a graph. One common way is to use a method called a "breadth-first search" starting from each point in the graph. This method systematically explores the graph layer by layer to find the shortest paths and, in turn, the shortest cycles.

Finding the girth can be a bit like solving a puzzle, but computers are very good at it, especially for smaller graphs.