McGee graph

McGee graph
The McGee graph
Named after	W. F. McGee
Vertices	24
Edges	36
Radius	4
Diameter	4
Girth	7
Automorphisms	32
Chromatic number	3
Chromatic index	3
Properties	Cubic Cage Hamiltonian

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, the graph is named after McGee who published the result in 1960. Then, the McGee graph was proven the unique (3,7)-cage by Tutte in 1966.

The McGee graph requires at least eight crossings in any drawing of it in the plane. It is one of five non-isomorphic graphs tied for being the smallest cubic graph that requires eight crossings. Another of these five graphs is the generalized Petersen graph G(12,5), also known as the Nauru graph.

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.

The characteristic polynomial of the McGee graph is : ${\displaystyle x^{3}(x-3)(x-2)^{3}(x+1)^{2}(x+2)(x^{2}+x-4)(x^{3}+x^{2}-4x-2)^{4}}$.

...
Wikipedia