TOPICS
Search

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 n edges is known as the match problem (Gardner 1991, pp. 79-81).

MatchstickGraphsByVertexCount

The numbers of connected matchstick graphs on n=1, 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 n=6 vertices, namely Y_3 which, as discussed further below, has both a planar embedding and a unit-distance embedding, but not a single embedding that is both.

MatchstickGraphsByEdgeCount

The numbers of connected matchstick graphs on n=1, 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. 3×n bishop, black bishop, and white bishop graphs,

2. non-overlapping braced polygons,

3. cycle graphs C_n,

4. empty graphs K^__n (trivially),

5. gear graphs,

6. Jahangir graphs J_(n,m) with n>1,

7. ladder graphs P_n square P_2,

8. ladder rung graphs nP_2,

9. pan graphs,

10. path graphs P_n,

11. polyhexes,

12. polyiamonds,

13. polyominoes,

14. Sierpiński carpet graphs,

15. Sierpiński gasket graphs,

16. star graphs S_n,

17. sunlet graphs C_n circledot K_1,

18. trees, and

19. triangular honeycomb acute knight graphs.

Nonmatchstick7Nodes

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 Y_n and Moser spindle. The sole 6-vertex connected planar unit-distance non-matchstick graph is the 3-prism graph Y_3. The numbers of connected graphs on n=1, 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.

MatchstickRegularGraphs

Consider minimal n-regular matchstick graphs, which are the smallest possible regular matchstick graph of vertex degree n. The minimal 1-regular matchstick graph is therefore the path graph P_2, the minimal 2-regular matchstick graph is the triangle graph C_3, 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 r-regular matchstick graphs are illustrated above and summarized in the table below.

nev
112
233
3128
410452

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 r-regular matchstick graphs can exist for r>5 (Kurz 2014), this establishes the non-existence of such graphs for r>=5.

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}].

MatchstickQuarticGraphs

Winkler et al. (2017) consider small matchstick graphs for which every vertex has degree m or n, 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.


See also

Braced Polygon, Harborth Graph, Match Problem, Regular Graph, Rigid Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Blokhuis, A. "Regular Finite Planar Maps with Equal Edges." Memorandum 1982-12. 2 Apr. 2019. https://arxiv.org/pdf/1401.1799.pdf.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.Cabello, S.; Demaine, E. D.; and Rote, G. "Planar Embeddings of Graphs with Specified Edge Lengths." J. Graph Algorithms Appl. 11, 259-276, 2007.Eades, P. and Wormald, N. C. "Fixed Edge-Length Graph Drawing Is NP-Hard." Discr. Appl. Math. 28, 111-134, 1990.Friedman, E. Problem 4 in "Math Magic: Problem of the Month (December 2005)." https://erich-friedman.github.io/mathmagic/1205.html.Gardner, M. "The Problem of the Six Matches." In The Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago University Press, pp. 79-81, 1991.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.Hartsfield, N. and Ringel, G. Pearls in Graph Theory: A Comprehensive Introduction, 2nd ed. San Diego, CA: Academic Press, 1994.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. Monthly 118, 264-267, 2011.Sloane, N. J. A. Sequences A066951 and A303792 in "The On-Line Encyclopedia of Integer Sequences."Salvia, R. "A Catalog of Matchstick Graphs." 5 Jan 2015. https://arxiv.org/abs/1303.5965.Update a linkTimm, M. "Diskrete Mathematik." http://www.mathematik.tu-bs.de/dm/Vaisse, A. "Matchstick Graphs." http://alexis.vaisse.monsite-orange.fr/page-54b81c6bc01a2.html.Winkler, M.; Dinkelacker, P.; and Vogel, S. "New Minimal (4;n)-Regular Matchstick Graphs." Geocombinatorics 27, 26-44, Jul. 2017.

Referenced on Wolfram|Alpha

Matchstick Graph

Cite this as:

Weisstein, Eric W. "Matchstick Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MatchstickGraph.html

Subject classifications