Herschel graph
Encyclopedia
In graph theory
, a branch of mathematics
, the Herschel graph is a bipartite
undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral
graph. It is named after British astronomer Alexander Stewart Herschel
, who wrote an early paper concerning William Rowan Hamilton
's icosian game
: the Herschel graph describes the smallest convex polyhedron for which this game has no solution. However, Herschel's paper described solutions for the Icosian game only on the graphs of the regular tetrahedron and regular icosahedron; it did not describe the Herschel graph.
: it can be drawn in the plane with none of its edges crossing. It is also 3-vertex-connected: the removal of any two of its vertices leaves a connected subgraph. Therefore, by Steinitz's theorem
, the Herschel graph is a polyhedral graph
: there exists a convex polyhedron (an enneahedron
) having the Herschel graph as its skeleton.
The Herschel graph is also a bipartite graph
: its vertices can be separated into two subsets of five and six vertices respectively, such that every edge has an endpoint in each subset (the red and blue subsets in the picture).
As with any bipartite graph, the Herschel graph is a perfect graph
: the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. It has also chromatic index 4, girth 4, radius 3 and diameter 4.
) but none with fewer edges.
All but three of the vertices of the Herschel graph have degree three; Tait's conjecture
states that a polyhedral graph in which every vertex has degree three
must be Hamiltonian, but this was disproved when W. T. Tutte
provided a counterexample, the much larger Tutte graph
. A refinement of Tait's conjecture, Barnette's conjecture
that every bipartite 3-regular polyhedral graph is Hamiltonian, remains open.
The Herschel graph also provides an example of a polyhedral graph for which the medial graph cannot be decomposed into two edge-disjoint Hamiltonian cycles. The medial graph of the Herschel graph is a 4-regular graph
with 18 vertices, one for each edge of the Herschel graph; two vertices are adjacent in the medial graph whenever the corresponding edges of the Herschel graph are consecutive on one of its faces.
and its full automorphism group is isomorphic to the dihedral group
of order 12, the group of symmetries of a regular hexagon, including both rotations and reflections. Every permutation of its three degree-four vertices can be realized by an automorphism of the graph, and there also exists a nontrivial automorphism that exchanges the remaining vertices while leaving the degree-four vertices unchanged.
The characteristic polynomial
of the Herschel graph is
.
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...
, a branch of mathematics
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...
, the Herschel graph is a bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
graph. It is named after British astronomer Alexander Stewart Herschel
Alexander Stewart Herschel
Professor Alexander Stewart Herschel was a British astronomer, born in Feldhausen, South Africa.He was the son of John Herschel and the grandson of William Herschel. Although much less well known than either of them, he did pioneering work in meteor spectroscopy. He also worked on identifying...
, who wrote an early paper concerning William Rowan Hamilton
William Rowan Hamilton
Sir William Rowan Hamilton was an Irish physicist, astronomer, and mathematician, who made important contributions to classical mechanics, optics, and algebra. His studies of mechanical and optical systems led him to discover new mathematical concepts and techniques...
's icosian game
Icosian game
The icosian game is a mathematical game invented in 1857 by William Rowan Hamilton. The game's object is finding a Hamiltonian cycle along the edges of a dodecahedron such that every vertex is visited a single time, no edge is visited twice, and the ending point is the same as the starting point...
: the Herschel graph describes the smallest convex polyhedron for which this game has no solution. However, Herschel's paper described solutions for the Icosian game only on the graphs of the regular tetrahedron and regular icosahedron; it did not describe the Herschel graph.
Properties
The Herschel graph is a planar graphPlanar 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...
: it can be drawn in the plane with none of its edges crossing. It is also 3-vertex-connected: the removal of any two of its vertices leaves a connected subgraph. Therefore, by Steinitz's theorem
Steinitz's theorem
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
, the Herschel graph is a polyhedral graph
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
: there exists a convex polyhedron (an enneahedron
Enneahedron
In geometry, a enneahedron is a polyhedron with 9 faces. There are 2606 topologically distinct enneahedra and none are regular, so this name is ambiguous.-Examples:...
) having the Herschel graph as its skeleton.
The Herschel graph is also a bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
: its vertices can be separated into two subsets of five and six vertices respectively, such that every edge has an endpoint in each subset (the red and blue subsets in the picture).
As with any bipartite graph, the Herschel graph is a perfect graph
Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
: the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. It has also chromatic index 4, girth 4, radius 3 and diameter 4.
Hamiltonicity
Because it is a bipartite graph that has an odd number of vertices, the Herschel graph does not contain a Hamiltonian cycle (a cycle of edges that passes through each vertex exactly once). For, in any bipartite graph, any cycle must alternate between the vertices on either side of the bipartition, and therefore must contain equal numbers of both types of vertex and must have an even length. Thus, a cycle passing once through each of the eleven vertices cannot exist in the Herschel graph. It is the smallest non-Hamiltonian polyhedral graph, whether the size of the graph is measured in terms of its number of vertices, edges, or faces; there exist other polyhedral graphs with 11 vertices and no Hamiltonian cycles (notably the Goldner–Harary graphGoldner–Harary graph
In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal planar graph...
) but none with fewer edges.
All but three of the vertices of the Herschel graph have degree three; Tait's conjecture
Tait's conjecture
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices...
states that a polyhedral graph in which every vertex has degree three
Cubic 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....
must be Hamiltonian, but this was disproved when W. T. Tutte
W. T. Tutte
William Thomas Tutte, OC, FRS, known as Bill Tutte, was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher, a major German code system, which had a significant impact on the Allied...
provided a counterexample, the much larger Tutte graph
Tutte graph
In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8....
. A refinement of Tait's conjecture, Barnette's conjecture
Barnette's conjecture
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W...
that every bipartite 3-regular polyhedral graph is Hamiltonian, remains open.
The Herschel graph also provides an example of a polyhedral graph for which the medial graph cannot be decomposed into two edge-disjoint Hamiltonian cycles. The medial graph of the Herschel graph is a 4-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 18 vertices, one for each edge of the Herschel graph; two vertices are adjacent in the medial graph whenever the corresponding edges of the Herschel graph are consecutive on one of its faces.
Algebraic properties
The Herschel graph is not a vertex-transitive graphVertex-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.\...
and 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...
of order 12, the group of symmetries of a regular hexagon, including both rotations and reflections. Every permutation of its three degree-four vertices can be realized by an automorphism of the graph, and there also exists a nontrivial automorphism that exchanges the remaining vertices while leaving the degree-four vertices unchanged.
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 Herschel graph is
.