In geometric graph theory

Geometric graph theory

In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...

, 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

Unit distance graph

In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one...

 and a plane graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

. Informally, matchstick graphs can be made by placing noncrossing matchsticks on a flat surface, hence the name.

It is known that there are matchstick graphs that are regular

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

 of any degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...

 up to 4. The complete graph

Complete graph

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

s and are 0-regular and 2-regular, respectively, and the path graph

Path graph

In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...

  is 1-regular. The smallest 3-regular matchstick graph is formed from two copies of the diamond graph

Diamond graph

In the mathematical field of graph theory, the diamond graph is a planar undirected graph with 4 vertices and 5 edges. It consists of a complete graph K_4 minus one edge....

 placed in such a way that corresponding vertices are at unit distance from each other; its bipartite double cover

Bipartite double cover

In graph theoretic mathematics, the bipartite double cover of an undirected graph G is a bipartite covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs G × K2...

 is the 8-crossed prism graph.

In 1986, Heiko Harborth

Heiko Harborth

Heiko Harborth is Professor of Mathematics at Braunschweig University of Technology, 1975–present, and author of more than 188 mathematical publications...

 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

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

 matchstick graph. It is a rigid graph.

There is a strong belief that there are no regular matchstick graphs of degree five, but the situation as of early 2010 seem to still be in flux with additional verification needed for the various proofs in circulation (cf. Blokhuis 2009, Kurz and Pinchasi 2009).
The smallest 3-regular matchstick graph without triangles (girth ≥ 4) has 20 vertices, as proved in 2009 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

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

to test whether a given undirected planar graph is a matchstick graph.