Wagner graph
Encyclopedia
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.
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 tree
s; it and the complete graph
K3,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
D8 of order 16, the group of symmetries of a octagon, including both rotations and reflections.
The characteristic polynomial
of the Wagner graph is
. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
The Wagner graph is triangle-free
and has independence number three, providing one half of the proof that the Ramsey number R(3,4) (the least number n such that any n-vertex graph contains either a triangle or a four-vertex independent set) is 9.
. The earliest result of this type is a 1937 theorem of Klaus Wagner
that graphs with no K5 minor can be formed by using clique-sum
operations to combine planar graphs and the Möbius ladder M8. For this reason M8 is called the Wagner graph.
The Wagner graph is also one of four minimal forbidden minors for the graphs of treewidth at most three (the other three being the complete graph
K5, 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 at most three (the other three being K5, the graph of the octahedron, and the cube graph.
Hamiltonian graph and can be defined by the LCF notation
[4]8.
It can be drawn as a ladder graph
with 4 rungs made cyclic on a topological Möbius strip
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Wagner graph is a 3-regular graph
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder
Möbius ladder
In graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle...
graph.
Properties
As a Möbius ladder, the Wagner graph is nonplanarPlanar graph
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...
but has crossing number
Crossing number (graph theory)
In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
one, making it an apex graph
Apex graph
In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. We say an apex, not the apex because an apex graph may have more than one apex...
. It can be embedded without crossings on a torus
Torus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
or projective plane
Projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect...
, so it is also a toroidal graph
Toroidal graph
In mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph's vertices can be placed on a torus such that no edges cross...
. It has girth 4, diameter 2, radius 2, chromatic number 3, chromatic index 3 and is both 3-vertex-connected
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
and 3-edge-connected
K-edge-connected graph
In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G = be an arbitrary graph....
.
The Wagner graph has 392 spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
s; it and the complete graph
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.-Properties:...
K3,3 have the most spanning trees among all cubic graphs with the same number of vertices.
The Wagner graph is a vertex-transitive graph
Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
but is not edge-transitive
Edge-transitive graph
In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....
. Its full automorphism group is isomorphic to the dihedral group
Dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
D8 of order 16, the group of symmetries of a octagon, including both rotations and reflections.
The characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
of the Wagner graph is
. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.The Wagner graph is triangle-free
Triangle-free graph
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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
and has independence number three, providing one half of the proof that the Ramsey number R(3,4) (the least number n such that any n-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 minorsMinor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
. The earliest result of this type is a 1937 theorem of Klaus Wagner
Klaus Wagner (mathematician)
Klaus Wagner was a German mathematician. He studied topology at the University of Cologne under the supervision of Karl Dörge, who had been a student of Issai Schur. Wagner received his Ph.D. in 1937, and taught at Cologne for many years himself...
that graphs with no K5 minor can be formed by using clique-sum
Clique-sum
In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology...
operations to combine planar graphs and the Möbius ladder M8. For this reason M8 is called the Wagner graph.
The Wagner graph is also one of four minimal forbidden minors for the graphs of treewidth at most three (the other three being the complete graph
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.-Properties:...
K5, the graph of the regular octahedron, and the graph of the pentagonal prism
Pentagonal prism
In geometry, the pentagonal prism is a prism with a pentagonal base. It is a type of heptahedron with 7 faces, 15 edges, and 10 vertices.- As a semiregular polyhedron :...
) and one of four minimal forbidden minors for the graphs of branchwidth at most three (the other three being K5, the graph of the octahedron, and the cube graph.
Construction
The Wagner graph is a cubicCubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
Hamiltonian graph and can be defined by the LCF notation
LCF notation
In combinatorial mathematics, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Coxeter and Frucht, for the representation of cubic graphs that are Hamiltonian. Since the graphs are Hamiltonian, the vertices can be arranged in a cycle, which accounts for two edges...
[4]8.
It can be drawn as a ladder graph
Ladder graph
In the mathematical field of graph theory, the ladder graph Ln is a planar undirected graph with 2n vertices and n+2 edges....
with 4 rungs made cyclic on a topological Möbius strip
Möbius strip
The Möbius strip or Möbius band is a surface with only one side and only one boundary component. The Möbius strip has the mathematical property of being non-orientable. It can be realized as a ruled surface...
.