TOPICS
Search

Harborth Graph


HarborthGraph

The Harborth graph is the smallest known 4-regular matchstick graph. It is therefore both planar and unit-distance. It has 104 edges and 52 vertices. This graph was named after its discoverer H. Harborth, who first presented it to a general public in 1986 (Harborth 1994, Petersen 1996, Gerbracht 2006, Winkler et al. 2017).

The Harborth graph is implemented in the Wolfram Language as GraphData["HarborthGraph"].

Analytic expressions for the vertices consisting of algebraic numbers of degree 22 (with large coefficients) were derived by Gerbracht (2006). As a consequence, Gerbracht (2006) also proved that the Harborth graph is rigid.


See also

Matchstick Graph, Regular Graph, Rigid Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Bode, J.-P.; Harborth, H.; and Thürmann, C. "Minimum Regular Rectilinear Plane Graph Drawings with Fixed Numbers of Edge Lengths." Congr. Numer. 169, 193-198, 2004.Gerbracht, E. H.-A. "Minimal Polynomials for the Coordinates of the Harborth Graph." Oct. 5, 2006. http://arxiv.org/abs/math.CO/0609360.Harborth, H. "Match Sticks in the Plane." In The Lighter Side of Mathematics. Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics & its History. Calgary, Canada, July 27-August 2, 1986 (Eds. R. K. Guy and R. E. Woodrow). Washington, DC: Math. Assoc. Amer., pp. 281-288, 1994.Harborth, H. and Kemnitz, A. "Integral Representations of Graphs." In Contemporary Methods in Graph Theory (Ed. R. Bodendiek). Mannheim, Germany: B.I.-Wissenschaftsverlag, pp. 359-367, 1990.Hartsfield, N. and Ringel, G. Pearls in Graph Theory: A Comprehensive Introduction. San Diego, CA: Academic Press, 1990.Kurz, S. "No Finite 5-Regular Matchstick Graph Exists." 8 Jan 2014. https://arxiv.org/abs/1401.1793.Kurz, S. and Pinchasi, R. "Regular Matchstick Graphs." Amer. Math. Monthly 118, 264-267, 2011.Pegg, E. Jr. "Material added 8 Jan 06 (Happy New Year)." http://www.mathpuzzle.com/26Feb2006.html.Peterson, I. "Mathland: Matchsticks in the Summer." August 1996. http://www.sciencenews.org/pages/sn_arch/8_10_96/mathland.htm.Winkler, M.; Dinkelacker, P.; and Vogel, S. "New Minimal (4;n)-Regular Matchstick Graphs." Geocombinatorics 27, 26-44, Jul. 2017.

Cite this as:

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

Subject classifications