View source for Herschel graph

{{Short description|Bipartite non-Hamiltonian polyhedral graph}}
{{infobox graph
 | name = Herschel graph
 | image = [[File:Herschel graph LS.svg|220px]]
 | image_caption = The Herschel graph.
 | namesake = Alexander Stewart Herschel
 | vertices = 11
 | edges = 18
 | automorphisms = 12 ([[Dihedral group|D]]<sub>6</sub>)
 | girth = 
 | diameter = 
 | radius = 
 | chromatic_number = 
 | chromatic_index = 
 | properties = {{plainlist|1=
*[[Polyhedral graph|Polyhedral]]
*[[Bipartite graph|Bipartite]]
*non-Hamiltonian
}}
}}

In [[Graph theory|graph theory]], a branch of [[Mathematics|mathematics]], the '''Herschel graph''' is a [[Bipartite graph|bipartite]] undirected graph with 11 vertices and 18 edges. It is a [[Polyhedral graph|polyhedral graph]] (the graph of a convex polyhedron), and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs (but not of this graph).

==Definition and properties==
The Herschel graph has three vertices of degree four (the three blue vertices aligned vertically in the center of the illustration) and eight vertices of degree three. Each two distinct degree-four vertices share two degree-three neighbors, forming a four-vertex cycle with these shared neighbors. There are three of these cycles, passing through six of the eight degree-three vertices (red in the illustration). Two more degree-three vertices (blue) do not participate in these four-vertex cycles; instead, each is adjacent to three of the six red vertices.{{r|clp}}

The Herschel graph is a [[Polyhedral graph|polyhedral graph]]; this means that it is a [[Planar graph|planar graph]], one that can be drawn in the plane with none of its edges crossing, and that it is [[Vertex connectivity|3-vertex-connected]]: the removal of any two of its vertices leaves a connected [[Glossary of graph theory#Subgraphs|subgraph]].{{r|clp}} It is a [[Bipartite graph|bipartite graph]]: when it is colored with five blue and six red vertices, as illustrated, each edge has one red endpoint and one blue endpoint.{{r|holton}}

It has order-6 dihedral symmetry, for a total of 12 members of its automorphism group. The degree-four vertices can be permuted arbitrarily, giving six permutations, and in addition, for each permutation of the degree-four vertices, there is a symmetry that keeps these vertices fixed and exchanges pairs of degree-three vertices.{{r|clp}}

==Polyhedron==
{{multiple image
|image1=Herschel enneahedron animated.gif|caption1=The Herschel graph as a polyhedron
|image2=Rectified triangular prism.png|caption2=The dual polyhedron, a [[Rectified prism|rectified triangular prism]]
|total_width=400}}
By [[Steinitz's theorem]], every graph that is planar and 3-vertex-connected has a convex polyhedron with the graph as its skeleton.{{r|grunbaum}} Because the Herschel graph has these properties,{{r|clp}} it can be represented in this way by a convex polyhedron, an [[Enneahedron|enneahedron]] having polyhedron has nine quadrilaterals as its faces.{{r|coxeter}} This can be chosen so that each [[Graph automorphism|graph automorphism]] corresponds to a symmetry of the polyhedron, in which case three of the faces will be [[Rhombus|rhombi]] or squares, and the other six will be [[Kite (geometry)|kites]].{{r|clp}}

The [[Dual polyhedron|dual polyhedron]] is a [[Rectified prism|rectified triangular prism]], which can be formed as the [[Convex hull|convex hull]] of the midpoints of the edges of a [[Triangular prism|triangular prism]]. When constructed in this way, it has three square faces on the same planes as the square faces of the prism, two [[Equilateral triangle|equilateral triangle]] faces on the planes of the triangular ends of the prism, and six more [[Isosceles triangle|isosceles triangle]] faces. This polyhedron has the property that its faces cannot be numbered in such a way that consecutive numbers appear on adjacent faces, and such that the first and last numbers are also on adjacent faces, because such a numbering would necessarily correspond to a Hamiltonian cycle in the Herschel graph. Polyhedral face numberings of this type are used as "spindown life counters" in the game ''Magic: The Gathering'', to track player lives, by turning the polyhedron to an adjacent face whenever a life is lost. A card in the game, the Lich, allows players to return from a nearly-lost state with a single life to their initial number of lives. Because the dual polyhedron for the Herschel graph cannot be numbered in such a way that this step connects adjacent faces, {{harvtxt|Constantinides|Constantinides|2018}} name the canonical polyhedron realization of this dual polyhedron as "the Lich's nemesis".{{r|concon}}

==Hamiltonicity==
[[File:Herschel Hamiltonian path.svg|thumb|A Hamiltonian path (but not cycle) in the Herschel graph]]
As 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. A graph is called Hamiltonian whenever it contains a Hamiltonian cycle, so the Herschel graph is not Hamiltonian. It has the smallest number of vertices, the smallest number of edges, and the smallest number of faces of any non-Hamiltonian polyhedral graph.{{r|barjuc}} There exist other polyhedral graphs with 11 vertices and no Hamiltonian cycles (notably the [[Goldner–Harary graph]]){{r|golhar}} but none with fewer edges.{{r|barjuc}}

All but three of the vertices of the Herschel graph have degree three. A graph is called [[Cubic graph|cubic]] or [[Regular graph|3-regular]] when all of its vertices have degree three. [[Tait's conjecture|P. G. Tait conjectured]]{{r|tait}} that a polyhedral 3-regular graph must be Hamiltonian; this was disproved when [[Biography:W. T. Tutte|W. T. Tutte]] provided a counterexample, the [[Tutte graph]], which is much larger than the Herschel graph.{{r|tutte}} A refinement of Tait's conjecture, [[Barnette's conjecture]] that every bipartite 3-regular polyhedral graph is Hamiltonian, remains open.{{r|garden}}

Every maximal planar graph that does not have a Hamiltonian cycle has a Herschel graph as a [[Graph minor|minor]]. The Herschel graph is conjectured to be one of three minor-minimal non-Hamiltonian 3-vertex-connected graphs. The other two are the [[Complete bipartite graph|complete bipartite graph]] <math>K_{3,4}</math> and a graph formed by splitting both the Herschel graph and <math>K_{3,4}</math> into two symmetric halves by three-vertex separators and then combining one half from each graph.{{r|dinmar}}

[[File:Medial Herschel graph.svg|thumb|The [[Medial graph|medial graph]] of the Herschel graph is a 4-regular [[Planar graph|planar graph]] with no [[Hamiltonian decomposition|Hamiltonian decomposition]]. The shaded regions correspond to the vertices of the underlying Herschel graph.]]
The Herschel graph also provides an example of a polyhedral graph for which the [[Medial graph|medial graph]] has no [[Hamiltonian decomposition]] into two edge-disjoint Hamiltonian cycles. The medial graph of the Herschel graph is a 4-[[Regular graph|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.{{r|bonhag}} It is [[K-vertex-connected graph|4-vertex-connected]] and ''essentially'' [[K-edge-connected graph|6-edge-connected]]. Here, a graph is <math>k</math>-vertex-connected or <math>k</math>-edge-connected if the removal of fewer than <math>k</math> vertices or edges (respectively) cannot disconnected it. Planar graphs cannot be 6-edge-connected, because they always have a vertex of degree at most five, and removing the neighboring edges disconnects the graph. The "essentially 6-edge-connected" terminology means that this trivial way of disconnecting the graph is ignored, and it is impossible to disconnect the graph into two subgraphs that each have at least two vertices by removing five or fewer edges.{{r|kirpet}}

==History==
The Herschel graph is named after Alexander Stewart Herschel, a British astronomer, who wrote an early paper concerning [[Biography:William Rowan Hamilton|William Rowan Hamilton]]'s [[Icosian game|icosian game]]. This is a puzzle involving finding Hamiltonian cycles on a polyhedron, usually the [[Regular dodecahedron|regular dodecahedron]]. The Herschel graph describes the smallest convex polyhedron that can be used in place of the dodecahedron to give a game that has no solution. Herschel's paper described solutions for the Icosian game only on the graphs of the regular tetrahedron and [[Regular icosahedron|regular icosahedron]]; it did not describe the Herschel graph.{{r|herschel}} The name "the Herschel graph" makes an early appearance in a graph theory textbook by John Adrian Bondy and [[Biography:U. S. R. Murty|U. S. R. Murty]], published in 1976.{{r|bonmur}} The graph itself was described earlier, for instance by H. S. M. Coxeter.{{r|coxeter}}

==References==
{{reflist|refs=

<ref name=barjuc>{{citation|title=Hamiltonian circuits on 3-polytopes|first1=David|last1=Barnette|first2=Ernest|last2=Jucovič|journal=Journal of Combinatorial Theory|volume=9|issue=1|year=1970|pages=54–59|doi=10.1016/S0021-9800(70)80054-0|doi-access=free}}.</ref>

<ref name=bonhag>{{citation|title= Edge-disjoint Hamilton cycles in 4-regular planar graphs|first1=J. A.|last1=Bondy|first2=R.|last2=Häggkvist|journal=[[Aequationes Mathematicae]]|volume=22|issue=1|year=1981|pages=42–45|doi=10.1007/BF02190157|s2cid=120729891 }}.</ref>

<ref name=bonmur>{{citation|last1=Bondy|first1=J. A.|last2=Murty|first2=U. S. R.|mr=0411988|page=53|publisher=North Holland|title=Graph Theory With Applications|year=1976}}</ref>

<ref name=clp>{{citation|url=http://aperiodical.com/2013/10/an-enneahedron-for-herschel/|title=An enneahedron for Herschel |last=Lawson-Perfect |first=Christian |date=13 October 2013 |website=The Aperiodical |access-date=7 December 2016}}</ref>

<ref name=concon>{{citation|last1=Constantinides|first1=Anthony F.|last2=Constantinides|first2=George A.|date=October 2018|doi=10.1017/mag.2018.111|issue=555|journal=The Mathematical Gazette|pages=447–453|title=Spindown Polyhedra|volume=102|s2cid=233357977 }}</ref>

<ref name=coxeter>{{citation|title=Regular Polytopes|first=H. S. M.|last=Coxeter|publisher=Methuen|location=London|year=1948|page=8}}</ref>

<ref name=dinmar>{{citation|last1=Ding|first1=Guoli|last2=Marshall|first2=Emily|doi=10.1007/s00373-018-1874-z|issue=2|journal=Graphs and Combinatorics|mr=3774453|pages=289–312|title=Minimal <math>k</math>-connected non-Hamiltonian graphs|volume=34|year=2018|s2cid=253891751 }}</ref>

<ref name=garden>{{citation|url=http://garden.irmacs.sfu.ca/?q=op/barnettes_conjecture |title=Barnette's conjecture|publisher=the Open Problem Garden|first=Robert |last=Šámal
|date=11 June 2007| accessdate=24 Feb 2011}}</ref>

<ref name=grunbaum>{{citation
 | contribution = 13.1 Steinitz's theorem
 | edition = 2nd
 | isbn = 0-387-40409-0
 | pages = 235–244
 | publisher = Springer-Verlag
 | series = [[Graduate Texts in Mathematics]]
 | title = Convex Polytopes
 | title-link = Convex Polytopes
 | volume = 221
 | year = 2003}}</ref>

<ref name=herschel>{{citation|last=Herschel|first=A. S.|title=Sir Wm. Hamilton's Icosian Game|url=https://books.google.com/books?id=-w8LAAAAYAAJ&pg=PA305|journal=The Quarterly Journal of Pure and Applied Mathematics|volume=5|page=305|year=1862}}</ref>

<ref name=holton>{{citation
 | last = Holton | first = D. A.
 | editor-last = Casse | editor-first = L. R. A.
 | contribution = Cycles in graphs
 | doi = 10.1007/BFb0071507
 | mr = 731570
 | pages = 24–48
 | publisher = Springer | location = Berlin
 | series = Lecture Notes in Mathematics
 | title = Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982
 | volume = 1036
 | isbn = 978-3-540-12708-6
 | year = 1983}}</ref>

<ref name=kirpet>{{citation|last1=Király|first1=Csaba|last2=Péterfalvi|first2=Ferenc|doi=10.1016/j.disc.2012.03.031|issue=15|journal=Discrete Mathematics|mr=2926099|pages=2262–2271|title=Balanced generic circuits without long paths|volume=312|year=2012|doi-access=free}}</ref>

<ref name=golhar>{{citation|first1=A.|last1=Goldner|first2=F.|last2=Harary|title=Note on a smallest nonhamiltonian maximal planar graph|journal=Bull. Malaysian Math. Soc.|volume=6|issue=1|year=1975|pages=41–42}}; see also the same journal '''6'''(2):33 (1975) and '''8''':104-106 (1977). Reference from [http://www.cs.nmsu.edu/fnh/publ.html listing of Harary's publications].</ref></ref>

<ref name=tait>{{citation|first=P. G.|last=Tait|title=Listing's ''Topologie''|url=https://books.google.com/books?id=8VMwAAAAIAAJ&pg=PA30|journal=[[Physics:Philosophical Magazine|Philosophical Magazine]] |series=5th Series|volume=17|year=1884|pages=30–46}}; see paragraph (16), pp. 41–42. Reprinted in ''Scientific Papers'', vol. II, pp. 85–98</ref>

<ref name=tutte>{{citation|first=W. T.|last=Tutte|title=On Hamiltonian circuits|year=1946| doi = 10.1112/jlms/s1-21.2.98|journal=Journal of the London Mathematical Society|volume=21|issue=2|pages=98–101}}</ref>

}}

==External links==
{{Commons}}
*{{mathworld|title=Herschel Graph|urlname=HerschelGraph|mode=cs2}}

[[Category:Individual graphs]]
[[Category:Planar graphs]]
[[Category:Hamiltonian paths and cycles]]

{{Sourceattribution|Herschel graph}}