In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the Heawood graph is an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

with 14 vertices and 21 edges, named after

Percy John Heawood Percy John Heawood (8 September 1861 – 24 January 1955) was a British mathematician, who concentrated on graph colouring. Life He was the son of the Rev. John Richard Heawood of Newport, Shropshire, and his wife Emily Heath, daughter of the ...

Combinatorial properties

The graph is

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 ...

, 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 A cage is an enclosure often made of mesh, bars, or wires, used to confine, contain or protect something or someone. A cage can serve many purposes, including keeping an animal or person in captivity, capturing an animal or person, and displayi ...

, the smallest cubic graph of

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

6. It is a

distance-transitive graph In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carri ...

(see the

Foster census In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

) and therefore distance regular. Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989) There are 24

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...

s in the Heawood graph; for each matching, the set of edges not in the matching forms a

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

. 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, 3-color its edges) in eight different ways. Every two perfect matchings, and every two Hamiltonian cycles, can be transformed into each other by a symmetry of the graph. 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 In the mathematics, mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic graph, cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter ...

Geometric and topological properties

The Heawood graph is a

toroidal graph In the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices and edges can be placed on a torus such that no edges intersect except at a vertex that belongs to bo ...

; that is, it can be embedded without crossings onto a

torus In geometry, a torus (: tori or toruses) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanarity, coplanar with the circle. The main types of toruses inclu ...

. The result is the regular map , with 7

hexagon In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A regular hexagon is de ...

al faces. Each face of the map is adjacent to every other face, thus as a result coloring the map requires 7 colors. The map and graph were discovered by

in 1890, who proved that no map on the torus could require more than seven colors and thus this map is maximal. The map can be faithfully realized as the

Szilassi polyhedron In geometry, the Szilassi polyhedron is a nonconvex polyhedron, topologically a Toroidal polyhedron, torus, with seven hexagon, hexagonal faces. The tetrahedron and the Szilassi polyhedron are the only two known polyhedra in which each face share ...

, the only known polyhedron apart from the

tetrahedron In geometry, a tetrahedron (: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular Face (geometry), faces, six straight Edge (geometry), edges, and four vertex (geometry), vertices. The tet ...

such that every pair of faces is adjacent.

The Heawood graph is the

Levi graph In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we ...

of the

Fano plane In finite geometry, the Fano plane (named after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and ...

, the graph representing incidences between points and lines in that geometry. With this interpretation, the 6-cycles in the Heawood graph correspond to

triangle A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called ''vertices'', are zero-dimensional points while the sides connecting them, also called ''edges'', are one-dimension ...

s in the Fano plane. Also, the Heawood graph is the

Tits building In mathematics, a building (also Tits building, named after Jacques Tits) is a combinatorial and geometric structure which simultaneously generalizes certain aspects of flag manifolds, finite projective planes, and Riemannian symmetric spaces. Bui ...

of the group SL₃(F₂). The Heawood graph has crossing number 3, and is the smallest cubic graph with that crossing number . 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 Colin de Verdière's invariant is a graph parameter \mu(G) for any Graph (discrete mathematics), graph ''G,'' introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certa ...

. The Heawood graph is a

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a Graph (discrete mathematics), graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly o ...

: 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.

Algebraic properties

The

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

of the Heawood graph is isomorphic to the

projective linear group In mathematics, especially in the group theoretic area of algebra, the projective linear group (also known as the projective general linear group or PGL) is the induced action of the general linear group of a vector space ''V'' on the associa ...

PGL₂(7), a group of order 336. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Heawood graph is a

symmetric graph In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. More strongly, the Heawood graph is 4-arc-transitive. According to the

, the Heawood graph, referenced as F014A, is the only cubic symmetric graph on 14 vertices. It has

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on ...

3 and

queue number In the mathematical field of graph theory, the queue number of a Graph (discrete mathematics), graph is a graph invariant defined analogously to book thickness, stack number (book thickness) using Queue (abstract data type), first-in first-out (q ...

2.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 The

characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...

of the Heawood graph is

(x-3) (x+3) (x^2-2)^6

. It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

Gallery

File:3-crossing Heawood graph.svg, crossing number 3 File:Heawood graph 3color edge.svg,

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge colorin ...

3 File:Heawood graph 2COL.svg,

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

2 File:7x-torus.svg, embedded in a torus ( shown as a square) File:Heawood graph and map on torus.png, embedded in a torus (compare

video Video is an Electronics, electronic medium for the recording, copying, playback, broadcasting, and display of moving picture, moving image, visual Media (communication), media. Video was first developed for mechanical television systems, whi ...

) File:Szilassi polyhedron.svg,

References

{{Commons Individual graphs Regular graphs