| McGee graph | |
| Namesake: | W. F. McGee |
| Vertices: | 24 |
| Edges: | 36 |
| Automorphisms: | 32 |
| Girth: | 7 |
| Diameter: | 4 |
| Radius: | 4 |
| Chromatic Number: | 3 |
| Chromatic Index: | 3 |
| Properties: | Cubic Cage Hamiltonian |
| Book Thickness: | 3 |
| Queue Number: | 2 |
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.
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,[1] the graph is named after McGee who published the result in 1960.[2] Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966.[3] [4] [5]
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, also known as the Nauru graph.[6] [7]
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.[8]
The characteristic polynomial of the McGee graph is
x3(x-3)(x-2)3(x+1)2(x+2)(x2+x-4)(x3+x2-4x-2)4
The automorphism group of the McGee graph is of order 32 and doesn't act transitively upon its vertices: there are two vertex orbits, of lengths 8 and 16. The McGee graph is the smallest cubic cage that is not a vertex-transitive graph.[9]