It corresponds to the seven-color torus map on 14 nodes illustrated above. The Heawood graph is the point/line incidence 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).
SEE ALSO: Cage Graph,
Fano Plane,
Heawood Four-Color Graph,
Moore Graph,
Szilassi
Polyhedron,
Torus Coloring
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.
Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs."
Bull. Amer. Math. Soc. 56, 413-455, 1950.
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/.
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.
CITE THIS AS:
Weisstein, Eric W. "Heawood Graph." From
MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HeawoodGraph.html
![[5,-5]^7](/National_Library/20160521004321im_/http://mathworld.wolfram.com/images/equations/HeawoodGraph/Inline1.gif)
.
.
-cage
graph and Moore graph.
Contact the MathWorld Team
heawood graph
