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 embeddings.

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. 2019).

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 incidence graphs of finite projective planes, the smallest example of which is the Heawood graph, were not unit-distance embeddable. The first explicit embedding refuting this conjecture was found by Gerbracht (2008), and exactly 11 such embeddings (illustrated above) were published by Gerbracht (2009) following a general outline first suggested by Harris (2007).

An apparent unit-distance embedding based on a central hexagon has also been constructed by E. Gerbracht (pers. comm., Jan. 2010).

Another unit-distance embedding has apparently been found by Horvat (2009), illustrated above.

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

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

See also

Cage Graph, Fano Plane, Foster Graph, Heawood Four-Color Graph, Honeycomb Toroidal Graph, Moore Graph, Smallest Cubic Crossing Number Graph, Szilassi Polyhedron, Torus Coloring

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236 and 244, 1976.Brouwer, A. E. "Heawood Graph." http://www.win.tue.nl/~aeb/drg/graphs/Heawood.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, pp. 209 and 221, 1989.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.Chvátal, V. Problem 21 in Chvátal, V.; Klarner, D. E.; and Knuth, D. E. "Selected Combinatorial Research Problems." Tech. Report STAN-CS-72-292, Computer Science Department, School of Humanities and Sciences. Stanford, CA: Stanford University, pp. 11-13, 1972.Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.DistanceRegular.org. "Heawood Graph Incidence Graph of Incidence Graph of Hadamard (7,3,1)-Design." https://www.math.mun.ca/distanceregular/graphs//heawood.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Heawood Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/heawood.gif.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Gerbracht, E. H.-A. "Eleven Unit Distance Embeddings of the Heawood Graph." Dec. 30, 2009. http://arxiv.org/abs/0912.5395.Gethner, E. and Springer, W. M. II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164, 159-175, 2003.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 173, 1994.Harris, M. A. "Toward a Unit Distance Embedding for the Heawood Graph." Nov. 7, 2007. http://arxiv.org/abs/math/0711.1157.Heawood, P. J. "Map-Colour Theorem." Quart. J. Math. Oxford Ser. 24, 332-338, 1890.Horvat, B. "Predstavitve grafov z enotsko razdaljo" ("Representations of Unit-Distance Graphs"). Ph.D. thesis, Faculty of Computer and Information Science. Ljubljana, Slovenia: University of Ljubljana, June 2009. http://eprints.fri.uni-lj.si/858/.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 271, 1998.Royle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.Royle, G. "F014A." http://www.csse.uwa.edu.au/~gordon/foster/F014A.html.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 192, 1990.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

Referenced on Wolfram|Alpha

Heawood Graph

Cite this as:

Weisstein, Eric W. "Heawood Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HeawoodGraph.html

Subject classifications