Heawood graph

From Wikipedia, the free encyclopedia

In the mathematical field of graph theory, the Heawood graph is the 6-cage, the smallest cubic graph of girth 6. It has 14 vertices and 21 edges, and is the Levi graph of the Fano plane. It is a distance-regular graph, with automorphism group PGL₂(7) (Brouwer).

There are 24 perfect matchings in the Heawood graph, each complementary to 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. It can be embedded into 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 this embedding, and another more symmetric embedding of the Heawood graph onto a torus.

[edit] References

• Brown, Ezra (2002). "The many names of (7,3,1)". Mathematics Magazine 75 (2): 83–94.

• Heawood, P. J. (1890). "Map colouring theorems". Quarterly J. Math. Oxford Ser. 24: 322–339.

[edit] External links

• Brouwer, Andries E.. Heawood graph. Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989).

• Weisstein, Eric W., Heawood Graph at MathWorld.