Girth (graph Theory) - Cages

Cages

A cubic graph (all vertices have degree three) of girth g – that is as small as possible – is known as a g-cage (or as a (3,g)-cage). The Petersen graph is the unique 5-cage (it is the smallest cubic graph of girth 5), the Heawood graph is the unique 6-cage, the McGee graph is the unique 7-cage and the Tutte eight cage is the unique 8-cage. There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10-cages, each with 70 vertices : 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