Match Problem

Author

Eric W. Weisstein
May 9, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/MatchProblem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/MatchProblem.html.

©2024 Wolfram Research, Inc. except for portions noted otherwise

Counts

<<MathWorld`Graphs`

https://arxiv.org/pdf/1303.5965

Matchstick graphs

A003055

Length/@(matches=Table[DeleteDuplicatesBy[MatchstickGraphs[n],CanonicalGraph[TopologicalGraph[#]]&],{n,10}])

BFileSequence[003055]

GraphData by EdgeCount

Complete up to 8 edges:

Length/@Table[DeleteDuplicatesBy[Select[GraphData[{"Connected","Matchstick"}],GraphData[#,"M"]==m&],CanonicalGraph[TopologicalGraph[GraphData[#]]]&],{m,10}]

Topologically distinct planar connected, unit distance graphs by EdgeCount

Length/@(planarconnected=Table[PlanarConnectedGraphs[n],{n,10}])//Timing

byedges=GroupBy[Join@@planarconnected,EdgeCount];//Timing

PlanarConnectedGraphsWithNEdges[n_]:=Lookup[byedges,n]

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:

Take[SortBy[Cases[GraphData[#,{"#","M","Planar","UnitDistance","Matchstick"}]&/@GraphData["Connected"],{gn_,m_,True,True,False}:>{m,gn}],First],20]

So starting at 9 edges, the following code can give false positives:

Length/@(matches=Table[DeleteDuplicatesBy[Select[PlanarConnectedGraphsWithNEdges[n],UnitDistanceGraphQ],CanonicalGraph[TopologicalGraph[#]]&],{n,9}])//Timing

Should be 1, 1, 3, 5, 10, 19, 39, 84, 196, 479, ... (A003055)

Figure

GraphicsGrid[Map[Annotate[#,VertexSize->.1]&,Take[matches,4],{2}],Dividers->All]

match[{v1_,v2_},e_]:=Module[{perp=.1RotationMatrix[π/2].Normalize[v2-v1]},{Opacity[1],EdgeForm[Black],{Darker@Red,Disk[v1-.05Normalize[v2-v1],.12]},FaceForm[LightYellow],Polygon[{v1+perp,v2+perp,v2-perp,v1-perp}]}]

CompleteGraph[3,EdgeShapeFunction->match,VertexSize->0]

GraphicsGrid[Map[Annotate[#,{EdgeShapeFunction->match,VertexSize->0}]&,Take[matches,4],{2}],Dividers->All,ImageSize->700]