Microsoft Store
 

Girth


 

Girth generally refers to the circumference of a cylindrical object, such as a tree trunk.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Graph theory - Cycle - 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.

Related Topics:
Petersen graph - Heawood graph - Tutte eight cage

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Image:Petersen graph.svg|The Petersen graph, of girth 5

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Image:Heawood graph.png|The Heawood graph, of girth 6

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Image:Tutte eight cage.png|The Tutte eight cage, of girth 8

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~