A matchstick graph is a unit distance graph without edge crossings. Informally, it is a graph which can be made of noncrossing matchsticks on a flat surface, hence the name.[1]
The simplest matchstick graphs are representations of complete graphs and and the path graph
In 1986, Heiko Harborth presented the graph that would bear his name, the Harborth Graph. It is the smallest known example of a 4-regular matchstick graph. It has 104 edges and 52 vertices.[2] It is a rigid graph.[3]
The bipartite double cover of the 3-regular matchstick graph is the 8-crossed prism graph.[1]
References
- ↑ a b Vorlage:Mathworld
- ↑ Harborth, H. "Match Sticks in the Plane." In The Lighter Side of Mathematics. Proceedings of the Eugéne Strens Memorial Conference of Recreational Mathematics and its History. Calgary, Canada, 1986 (Eds. R. K. Guy and R. E. Woodrow). Washington, DC: Mathematical Association of America, pp. 281-288, 1994, as cited in: Vorlage:Mathworld
- ↑ Gerbracht, E. H.-A. "Minimal Polynomials for the Coordinates of the Harborth Graph." Oct. 5, 2006 , as cited in: Vorlage:Mathworld