Heawood Graph - Geometric and Topological Properties

Geometric and Topological Properties

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 graph is named after Percy John Heawood, who in 1890 proved that in every subdivision of the torus into polygons, the polygonal regions 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 is also the Levi graph of the Fano plane, the graph representing incidences between points and lines in that geometry. With this interpretation, the 6-cycles in the Heawood graph correspond to triangles in the Fano plane.

The Heawood graph has crossing number 3, and is the smallest cubic graph with that crossing number (sequence A110507 in OEIS). Including the Heawood graph, there are 8 distinct graphs of order 14 with crossing number 3.

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. However, the known embeddings of this type lack any of the symmetries that are inherent in the graph.