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 Wagner graph is a 3- regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

Properties

As a Möbius ladder, the Wagner graph is

nonplanar In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...

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 of order 16, the group of symmetries of an octagon, including both rotations and reflections. The characteristic polynomial of the Wagner graph is :

(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 A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of color ...

. The Wagner graph is

triangle-free In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...

and has

independence number Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...

three, providing one half of the proof that the Ramsey number (the least number such that any -vertex graph contains either a triangle or a four-vertex independent set) is 9.

Graph minors

Möbius ladders play an important role in the theory of

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...

s. The earliest result of this type is a 1937 theorem of Klaus Wagner (part of a cluster of results known as

Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on f ...

) that graphs with no ''K''₅ minor can be formed by using clique-sum operations to combine planar graphs and the Möbius ladder ''M''₈. For this reason ''M''₈ is called the Wagner graph. The Wagner graph is also one of four minimal

forbidden minor In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...

s for the graphs of treewidth at most three (the other three being the

''K''₅, the graph of the regular octahedron, and the graph of the pentagonal prism) and one of four minimal forbidden minors for the graphs of

branchwidth In graph theory, a branch-decomposition of an undirected graph ''G'' is a hierarchical clustering of the edges of ''G'', represented by an unrooted binary tree ''T'' with the edges of ''G'' as its leaves. Removing any edge from ''T'' partitions ...

at most three (the other three being ''K''₅, the graph of the octahedron, and the

cube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, ...

Construction

The Wagner graph is a

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

Hamiltonian graph and can be defined by the LCF notation sup>8. It is an instance of an

Andrásfai graph In graph theory, an Andrásfai graph is a triangle-free graph, triangle-free, circulant graph named after Béla Andrásfai. Properties The Andrásfai graph for any natural number is a circulant graph on vertices, in which vertex is conne ...

, a type of circulant graph in which the vertices can be arranged in a cycle and each vertex is connected to the other vertices whose positions differ by a number that is 1 (mod 3). It is also isomorphic to the

circular clique In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The ''circular chromatic number'' of a graph G, denoted \chi_c(G) can be given by any of the following definitions, all of whi ...

. It can be drawn as a

ladder graph In the mathematical field of graph theory, the ladder graph is a planar, undirected graph with vertices and edges. The ladder graph can be obtained as the Cartesian product of two path graphs, one of which has only one edge: . Propertie ...

with 4 rungs made cyclic on a topological Möbius strip.

Gallery

Image:Wagner graph 3COL.svg, The chromatic number of the Wagner graph is 3. Image:Wagner graph 3color edge.svg, The chromatic index of the Wagner graph is 3. Image:Möbius_ladder_on_Möbius_strip.svg, The Wagner graph drawn on the Möbius strip.

References

{{reflist Individual graphs Regular graphs