McGee graph
Introduction 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 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.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.
Algebraic properties The characteristic polynomial of the McGee graph is :. 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.
Gallery Image:McGee graph crossing number.svg|The crossing number of the McGee graph is 8.Image:McGee graph 3COL.svg |The chromatic number of the McGee graph is 3.Image:McGee graph  3color edge.svg|The chromatic index of the McGee graph is 3.Image:Acyclic_coloring.svg|The acyclic chromatic number of the McGee graph is 3.Image:McGee graph.svg|Alternative drawing of the McGee graph.
References