In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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 In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

3 and

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

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 In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the McGee graph is :

x^3(x-3)(x-2)^3(x+1)^2(x+2)(x^2+x-4)(x^3+x^2-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 In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive ...

.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.

Gallery

Image:McGee graph crossing number.svg, The crossing number of the McGee graph is 8. Image:McGee graph 3COL.svg , The

of the McGee graph is 3. Image:McGee graph 3color edge.svg, The

of the McGee graph is 3. Image:Acyclic_coloring.svg, The

acyclic chromatic number In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number of a graph is the fewest colors needed in any acyclic coloring of . Acyclic coloring is often as ...

of the McGee graph is 3. Image:McGee graph.svg, Alternative drawing of the McGee graph.

References

{{reflist Individual graphs Regular graphs