Wagner graph

Wagner graph
The Wagner graph
Named after	Klaus Wagner
Vertices	8
Edges	12
Radius	2
Diameter	2
Girth	4
Automorphisms	16 (D8)
Chromatic number	3
Chromatic index	3
Genus	1
Properties	Cubic Hamiltonian Triangle-free Vertex-transitive Toroidal Apex
Notation	M8

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, making it an apex graph. It can be embedded without crossings on a torus or projective plane, so it is also a toroidal graph. It has girth 4, diameter 2, radius 2, chromatic number 3, chromatic index 3 and is both 3-vertex-connected and 3-edge-connected.

The Wagner graph has 392 spanning trees; it and the complete graph K_3,3 have the most spanning trees among all cubic graphs with the same number of vertices.

The Wagner graph is a vertex-transitive graph but is not edge-transitive. Its full automorphism group is isomorphic to the dihedral group D₈ of order 16, the group of symmetries of an octagon, including both rotations and reflections.

The characteristic polynomial of the Wagner graph is ${\displaystyle (x-3)(x-1)^{2}(x+1)(x^{2}+2x-1)^{2}}$. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

...
Wikipedia