Girth
|
|
In graph theory, the girth of a graph is the length of the shortest cycle contained in the graph. If the graph doesn't contain any cycles, its girth is defined to be infinity.
For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3.
The Petersen graph is the smallest trivalent graph with girth 5. The Heawood graph is the smallest trivalent graph with girth 6. The Tutte eight cage is the smallest trivalent graph with girth 8.
Missing image
Petersen_graph.png
Petersen_graph.png
The Petersen graph, of girth 5
Missing image
Heawood_graph.png
Heawood_graph.png
The Heawood graph, of girth 6
Missing image
Tutte_eight_cage.png
Tutte_eight_cage.png
The Tutte eight cage, of girth 8
In common usage, girth refers to the circumference of a cylindrical object such as a tree trunk.