McGee graph | |
---|---|
Named after | W. F. McGee |
Vertices | 24 |
Edges | 36 |
Radius | 4 |
Diameter | 4[1] |
Girth | 7[1] |
Automorphisms | 32[1] |
Chromatic number | 3[1] |
Chromatic index | 3[1] |
Book thickness | 3 |
Queue number | 2 |
Properties | Cubic Cage Hamiltonian |
Table of graphs and parameters |
In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges.[1]
The McGee graph is the unique (3,7)-cage (the smallest cubic graph of girth 7). It is also the smallest cubic cage that is not a Moore graph.
First discovered by Sachs but unpublished,[2] the graph is named after McGee who published the result in 1960.[3] Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966.[4][5][6]
The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of three non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these three graphs is the generalized Petersen graph G(12,5), also known as the Nauru graph.[7][8]
The McGee graph has radius 4, diameter 4, chromatic number 3 and chromatic index 3. It is also a 3-vertex-connected and a 3-edge-connected graph. It has book thickness 3 and queue number 2.[9]