Editing Heawood graph

{{distinguish|text = the [[Heawood graphs]], a graph family that contains the Heawood graph}}

{{Short description|Undirected graph with 14 vertices}}
{{Infobox graph
 | name = Heawood graph
 | image = [[Image:Heawood_Graph.svg|180px]]
 | image_caption = 
 | namesake = [[Percy John Heawood]]
 | vertices = 14
 | edges = 21
 | girth = 6
 | diameter = 3
 | radius = 3
 | genus = 1
 | automorphisms = 336 ([[Projective linear group|PGL<sub>2</sub>(7)]])
 | chromatic_number = 2 
 | chromatic_index = 3
 | properties = [[Bipartite graph|Bipartite]]<br>[[Cubic graph|Cubic]]<br>[[Cage (graph theory)|Cage]]<br>[[Distance-transitive graph|Distance-transitive]]<br>[[Distance-regular graph|Distance-regular]]<br>[[Toroidal graph|Toroidal]]<br>[[Hamiltonian graph|Hamiltonian]]<br>[[Symmetric graph|Symmetric]]<br>Orientably simple
|book thickness=3|queue number=2}}

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Heawood graph''' is an [[undirected graph]] with 14 vertices and 21 edges, named after [[Percy John Heawood]].<ref>{{MathWorld | urlname=HeawoodGraph | title=Heawood Graph}}</ref>

==Combinatorial properties==
The graph is [[cubic graph|cubic]], and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-[[cage (graph theory)|cage]], the smallest cubic graph of [[girth (graph theory)|girth]] 6. It is a [[distance-transitive graph]] (see the [[Foster census]]) and therefore [[Distance-regular graph|distance regular]].<ref name="brouwer">{{cite web | author=Brouwer, Andries E. | authorlink = Andries Brouwer | title = Heawood graph | url = http://www.win.tue.nl/~aeb/drg/graphs/Heawood.html}} Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989)</ref>

There are 24 [[perfect matching]]s in the Heawood graph; for each matching, the set of edges not in the matching forms a [[Hamiltonian cycle]]. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is, [[Edge coloring|3-color its edges]]) in eight different ways.<ref name="brouwer"/> Every two perfect matchings, and every two Hamiltonian cycles, can be transformed into each other by a symmetry of the graph.<ref>{{citation
 | last1 = Abreu | first1 = M.
 | last2 = Aldred | first2 = R. E. L.
 | last3 = Funk | first3 = M.
 | last4 = Jackson | first4 = Bill
 | last5 = Labbate | first5 = D.
 | last6 = Sheehan | first6 = J.
 | doi = 10.1016/j.jctb.2004.09.004
 | mr = 2099150
 | issue = 2
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | pages = 395–404
 | title = Graphs and digraphs with all 2-factors isomorphic
 | volume = 92
 | year = 2004| doi-access = free
 }}.</ref>

There are 28 six-vertex cycles in the Heawood graph. Each 6-cycle is disjoint from exactly three other 6-cycles; among these three 6-cycles, each one is the symmetric difference of the other two. The graph with one node per 6-cycle, and one edge for each disjoint pair of 6-cycles, is the [[Coxeter graph]].<ref>{{citation|first=Italo J.|last=Dejter|title=From the Coxeter graph to the Klein graph|journal=Journal of Graph Theory|year=2011|volume=70|pages=1–9|doi=10.1002/jgt.20597|arxiv=1002.1960|s2cid=754481}}.</ref>

==Geometric and topological properties==
[[Image:Heawood map on a hexagon.svg|upright=1|thumb|left|Heawood's map. Opposite edges of the large hexagon are connected to form a torus.]]
The Heawood graph is a [[toroidal graph]]; that is, it can be [[Graph embedding|embedded]] without crossings onto a [[torus]]. The result is the [[Regular map (graph theory)|regular map]] {{math|{6,3}{{sub|2,1}}}}, with 7 [[hexagon]]al faces.<ref name="Coxeter">{{citation|last=Coxeter|author-link=Harold Scott MacDonald Coxeter|year=1950|title=Self-dual configurations and regular graphs|journal=Bulletin of the American Mathematical Society|doi=10.1090/S0002-9904-1950-09407-5|url=https://www.ams.org/journals/bull/1950-56-05/S0002-9904-1950-09407-5/S0002-9904-1950-09407-5.pdf|volume=56}}</ref> Each face of the map is adjacent to every other face, thus as a result [[Map coloring (mathematics)|coloring]] the map requires 7 colors. The map and graph were discovered by [[Percy John Heawood]] in 1890, who proved that no map on the torus could require more than seven colors and thus this map is maximal.<ref>{{cite journal | doi=10.2307/3219140 | author=Brown, Ezra | title=The many names of (7,3,1) | journal=[[Mathematics Magazine]] | volume=75 | issue=2 | year=2002 | pages=83–94 | url=http://www.math.vt.edu/people/brown/doc/731.pdf | jstor=3219140 | access-date=2006-10-27 | archive-url=https://web.archive.org/web/20120205095819/http://www.math.vt.edu/people/brown/doc/731.pdf | archive-date=2012-02-05 | url-status=dead }}</ref><ref>{{cite journal | author=Heawood, P. J. | authorlink=Percy John Heawood | title=Map-colour theorem | journal = Quarterly Journal of Mathematics |series=First Series | year=1890 | volume=24 | pages=322–339}}</ref>

The map can be faithfully realized as the [[Szilassi polyhedron]],<ref>{{citation |last = Szilassi |first = Lajos |journal = Structural Topology |pages = 69–80 |title = Regular toroids |url = http://www-iri.upc.es/people/ros/StructuralTopology/ST13/st13-06-a3-ocr.pdf |volume = 13 |year = 1986}}</ref> the only known polyhedron apart from the [[tetrahedron]] such that every pair of faces is adjacent.

<div class=skin-invert-image>{{multiple image
 | align = right | perrow = 2 | total_width = 300
 | image1 = Fano plane nimbers.svg
 | image2 = Heawood Levi Fano.svg
 | image3 = Heawood Levi Fano bipartite.svg
 | footer = [[Fano plane]] and two representations of its [[Levi graph]] <small>(below as a [[bipartite graph]])</small>
}}</div>

The Heawood graph is the [[Levi graph]] of the [[Fano plane]],<ref name="Coxeter"/> the graph representing incidences between points and lines in that geometry. With this interpretation, the 6-cycles in the Heawood graph correspond to [[triangle]]s in the Fano plane. Also, the Heawood graph is the [[Tits building]] of the group [[GL(3,2)|SL<sub>3</sub>(F<sub>2</sub>)]].

The Heawood graph has [[Crossing number (graph theory)|crossing number]] 3, and is the smallest cubic graph with that crossing number {{OEIS|id=A110507}}. Including the Heawood graph, there are 8 distinct graphs of order 14 with crossing number 3.

The Heawood graph is the smallest cubic graph with [[Colin de Verdière graph invariant]] {{math|μ {{=}} 6}}.<ref>{{cite journal | doi=10.1016/j.jctb.2005.09.004 | author=Hein van der Holst | title=Graphs and obstructions in four dimensions | journal=[[Journal of Combinatorial Theory, Series B]] | volume=96 | issue=3 | year=2006 | pages=388–404 | url=https://core.ac.uk/download/pdf/82523665.pdf| doi-access=free }}</ref>

The Heawood graph is a [[unit distance graph]]: it can be embedded in the plane such that adjacent vertices are exactly at distance one apart, with no two vertices embedded to the same point and no vertex embedded into a point within an edge.<ref>{{Citation | last = Gerbracht | first = Eberhard H.-A. | title = Eleven unit distance embeddings of the Heawood graph | year = 2009 | arxiv = 0912.5395| bibcode = 2009arXiv0912.5395G }}.</ref>

==Algebraic properties==
The [[automorphism group]] of the Heawood graph is isomorphic to the [[projective linear group]] PGL<sub>2</sub>(7), a group of order 336.<ref>{{cite book|last1=Bondy|first1=J. A.|author1-link=John Adrian Bondy|last2=Murty|first2=U. S. R.|author2-link=U. S. R. Murty|title=Graph Theory with Applications|location=New York|publisher=North Holland|year=1976|page=[https://archive.org/details/graphtheorywitha0000bond/page/237 237]|isbn=0-444-19451-7|url=https://archive.org/details/graphtheorywitha0000bond/page/237|url-status=dead|access-date=2019-12-18|archive-url=https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html|archive-date=2010-04-13}}</ref> It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Heawood graph is a [[symmetric graph]]. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. 
More strongly, the Heawood graph is [[Symmetric graph|4-arc-transitive]].<ref>{{cite journal|last1=Conder|first1=Marston|last2=Morton|first2=Margaret|title=Classification of Trivalent Symmetric Graphs of Small Order|journal=Australasian Journal of Combinatorics|date=1995|volume=11|pages=146|url=https://ajc.maths.uq.edu.au/pdf/11/ocr-ajc-v11-p139.pdf}}</ref>
According to the [[Foster census]], the Heawood graph, referenced as F014A, is the only cubic symmetric graph on 14 vertices.<ref>Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census "Cubic Symmetric Graphs (The Foster Census)."] {{webarchive|url=https://web.archive.org/web/20080720005020/http://www.cs.uwa.edu.au/~gordon/remote/foster/ |date=2008-07-20 }}</ref><ref>[[Marston Conder|Conder, M.]] and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.</ref>

It has [[book thickness]] 3 and [[queue number]] 2.<ref>Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018</ref>

The [[characteristic polynomial]] of the Heawood graph is <math>(x-3) (x+3) (x^2-2)^6</math>. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

==Gallery==
<gallery class="skin-invert-image">
File:3-crossing Heawood graph.svg|[[Crossing number (graph theory)|crossing number]] 3
File:Heawood graph 3color edge.svg|[[chromatic index]] 3
File:Heawood graph 2COL.svg|[[chromatic number]] 2
File:7x-torus.svg|embedded in a torus <small>([[periodic boundary conditions|shown as a square]])</small>
File:Heawood graph and map on torus.png|embedded in a torus (compare [[:File:Heawood_graph_on_torus.webm|video]])
File:Szilassi polyhedron.svg|[[Szilassi polyhedron]]
</gallery>

== References ==
{{reflist}}
{{Commons}}

[[Category:Individual graphs]]
[[Category:Regular graphs]]