Matchstick graph
| Harborth graph | |
|---|---|
 |
|
| Vertices | 52 |
| Edges | 104 |
| Radius | 6 |
| Diameter | 9 |
| Girth | 3 |
In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an embedding which is simultaneously a unit distance graph and a plane graph. Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name.
Much of the research on matchstick graphs has concerned regular graphs, in which each vertex has the same number of neighbors. This number is called the degree of the graph.
It is known that there are matchstick graphs that are regular of any degree up to 4. The complete graphs with one, two, and three vertices (a single vertex, a single edge, and a triangle) are all matchstick graphs and are 0-, 1-, and 2-regular respectively. The smallest 3-regular matchstick graph is formed from two copies of the diamond graph placed in such a way that corresponding vertices are at unit distance from each other; its bipartite double cover is the 8-crossed prism graph.
In 1986, Heiko Harborth presented the graph that would bear his name, the Harborth Graph. With 104 edges and 52 vertices, is the smallest known example of a 4-regular matchstick graph. It is a rigid graph.
It is not possible for a regular matchstick graph to have degree greater than four.
The smallest 3-regular matchstick graph without triangles (girth ≥ 4) has 20 vertices, as proved by Kurz and Mazzuoccolo. Furthermore, they exhibit the smallest known example of a 3-regular matchstick graph of girth 5 (180 vertices).
It is NP-hard to test whether a given undirected planar graph can be realized as a matchstick graph. More precisely, this problem is complete for the existential theory of the reals.Kurz (2014) provides some easily tested necessary criteria for a graph to be a matchstick graph, but these are not also sufficient criteria: a graph may pass Kurz's tests and still not be a matchstick graph.
...
Wikipedia