Matchstick Graph

A matchstick graph is a simple graph which has a graph embedding that is planar, for which all distances between vertices have unit distance, and which is non-degenerate (so no vertices are coincident, no edges cross or overlap, and no vertices are coincident with edges on which they are not incident).

The problem of finding the number of topologically distinct matchstick graphs on edges is known as the match problem (Gardner 1991, pp. 79-81).

The numbers of connected matchstick graphs on , 2, ... nodes are 1, 1, 2, 5, 13, 50, ... (OEIS A303792; E. Weisstein, Apr. 30, 2018), the first few of which are illustrated above. There is one fewer connected 6-matchstick graph than connected unit-distance graphs on vertices, namely which, as discussed further below, has both a planar embedding and a unit-distance embedding, but not a single embedding that is both.

The numbers of connected matchstick graphs on , 2, ... edges are 1, 1, 3, 5, 12, 28, 74, 207, 633, 2008, ... (OEIS A066951; Salvia 2015, Vaisse), the first few of which are illustrated above.

It is NP-hard to test is a graph is matchstick (Eades and Wormland 1990, Cabello et al. 2007, Salvia 2015).

Classes of graphs that are matchstick graphs include the following:

1. bishop, black bishop, and white bishop graphs,

2. non-overlapping braced polygons,

3. cycle graphs ,

4. empty graphs (trivially),

5. gear graphs,

6. Jahangir graphs with ,

7. ladder graphs ,

8. ladder rung graphs ,

9. pan graphs,

10. path graphs ,

11. polyhexes,

12. polyiamonds,

13. polyominoes,

14. Sierpiński carpet graphs,

15. Sierpiński gasket graphs,

16. star graphs ,

17. sunlet graphs ,

18. trees, and

19. triangular honeycomb acute knight graphs.

A matchstick graph is both planar and unit-distance, but a planar unit-distance graph may fail to be a matchstick graph if a single embedding cannot be constructed having both properties. Examples include the prism graphs and Moser spindle. The sole 6-vertex connected planar unit-distance non-matchstick graph is the 3-prism graph . The numbers of connected graphs on , 2, ... vertices that are planar and unit-distance but not matchstick are 0, 0, 0, 0, 0, 1, 11, ... (E. Weisstein, Jan. 2, 2022), where the 7-vertex examples are illustrated above.

Consider minimal -regular matchstick graphs, which are the smallest possible regular matchstick graph of vertex degree . The minimal 1-regular matchstick graph is therefore the path graph , the minimal 2-regular matchstick graph is the triangle graph , and the minimal 3-regular matchstick graph is the 8-vertex graph illustrated above. The smallest known 4-regular matchstick graph is the Harborth graph on 104 edges and 52 vertices (Hartsfield and Ringel 1994; Timm). While the Harborth graph has not been proven optimal, Kurz and Pinchasi (2011) showed that every 4-regular matchstick graph in the plane contains at least 20 vertices. The smallest known -regular matchstick graphs are illustrated above and summarized in the table below.

Over the years, several unpublished proofs for the nonexistence of a quintic matchstick graph have appeared (cf. Friedman 2005). Kurz and Pinchasi (2011) settled the question by proving that no quintic matchstick graph exists. Since Euler's polyhedral formula means no -regular matchstick graphs can exist for (Kurz 2014), this establishes the non-existence of such graphs for .

The minimal (or, in the case of the Harborth graph, conjectured minimal) regular matchstick graphs are implemented in the Wolfram Language as GraphData["MinimalRegularMatchstick", n].

Winkler et al. (2017) consider small matchstick graphs for which every vertex has degree or , as well as additional quartic matchstick graphs that are slightly larger than the Harborth graph, illustrated above.

The bipartite double graph of the minimal 3-regular matchstick graph is the 8-crossed prism graph.