Heawood graph

From Wikipedia, the free encyclopedia

The Heawood graph.

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges. Each vertex is adjacent to exactly three edges (that is, it is a cubic graph), 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.

[edit] 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. The images below show both this embedding, and another more symmetric embedding of the Heawood graph onto a smooth torus.