The Harborth graph is the smallest known 4-regularmatchstick 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).
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.
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. Monthly118,
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 -Regular Matchstick Graphs." Geocombinatorics27,
26-44, Jul. 2017.
-Regular Matchstick Graphs." Geocombinatorics 27,
26-44, Jul. 2017.