Heawood graph

infobox graph
name = Heawood graph


image_caption =
namesake = Percy John Heawood
vertices = 14
edges = 21
girth = 6
chromatic_number = 2
chromatic_index = 3
properties = Cubic Cage Distance-regular Toroidal

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges. The graph is 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, the smallest cubic graph of girth 6. It is also the Levi graph of the Fano plane, the graph representing incidences between points and lines in that geometry. It is a distance-regular graph; its group of symmetries is PGL₂(7) (Brouwer).

There are 24 perfect matchings 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, 3-color its edges) in eight different ways (Brouwer).

The Heawood graph is named after Percy John Heawood, who in 1890 proved that every subdivision of the torus into polygons can be colored by at most seven colors. The Heawood graph forms a subdivision of the torus with seven mutually-adjacent regions, showing that this bound is tight.

The Heawood graph has crossing number 3, and is the smallest cubic graph with that crossing number OEIS|id=A110507.

Torus embedding

The Heawood graph is a toroidal graph; that is, it can be embedded without crossings onto a torus. One embedding of this type places its vertices and edges into three-dimensional Euclidean space as the set of vertices and edges of a nonconvex polyhedron with the topology of a torus, the Szilassi polyhedron.

References

*

*

External links

*

*