Harborth Graph
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).
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
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. https://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)." https://www.mathpuzzle.com/26Feb2006.html.
Peterson, I. "Mathland: Matchsticks in the Summer." August 1996. https://www.sciencenews.org/pages/sn_arch/8_10_96/mathland.htm.
CITE THIS AS:
Weisstein, Eric W. "Harborth Graph." From
MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HarborthGraph.html
Contact the MathWorld Team
harborth graph
