Heawood Graph

The Heawood graph is a cubic graph on 14 vertices and 21 edges which is the unique (3,6)-cage graph. It is also a Moore graph. It has graph diameter 3, graph radius 3, and girth 6. It is cubic symmetric, nonplanar, Hamiltonian, and can be represented in LCF notation as . The Heawood graph is illustrated above in a number of drawings.

The Heawood graph is isomorphic to the generalized hexagon , Knödel graph , and honeycomb toroidal graph . The line graph is the generalized hexagon .

It has chromatic number 2 and chromatic polynomial

Its graph spectrum is .

It is 4-transitive, but not 5-transitive (Harary 1994, p. 173).

The Heawood graph is one of eight cubic graphs on 14 nodes with smallest possible graph crossing number of 3 (another being the generalized Petersen graph ), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2020).

The Heawood graph is the second of four graphs depicted on the cover of Harary (1994).

The Heawood graph corresponds to the seven-color torus map on 14 nodes illustrated above. The Heawood graph is the point/line Levi graph on the Fano plane (Royle).

Chvátal (1972) conjectured that point-line Levi graphs of finite projective planes, the smallest example of which is the Heawood graph, were not unit-distance graphs. The first explicit graph drawing refuting this conjecture was found by Gerbracht (2008), and exactly 11 such drawings (illustrated above) were published by Gerbracht (2009) following a general outline first suggested by Harris (2007). Additional unit-distance embeddings based on a central hexagon were also constructed by E. Gerbracht (pers. comm., Jan. 2010) and Horvat (2009).

The Heawood graph is toroidal, as illustrated above. The left-hand drawing shows an graph embedding in a fundamental region whose paired boundary sides are identified to form a torus. The right-hand drawing shows a finite patch of the corresponding periodic lift, illustrating how edges continue across these boundaries and where corresponding vertices in different regions represent the same vertex on the torus.

The Heawood graph has projective plane crossing number 2. If a one-crossing drawing existed, deleting one crossed edge would embed a 14-vertex, 20-edge subgraph of girth at least 6 in the projective plane. However, the Euler characteristic formula and the face-length bound would give , giving the contradiction . Thus the drawing illustrated above is minimal.

It is implemented in the Wolfram Language as GraphData["HeawoodGraph"].