Bounding the Number of Edges of Matchstick Graphs
Jérémy Lavollée, Konrad J. Swanepoel · SIAM Journal on Discrete Mathematics · 2022
A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth conjectured in 1981 that the maximum number of edges of a matchstick graph with $n$ vertices is $\lfloor 3n-\sqrt{12n-3}\rfloor$. Using the Euler formula and the isoperimetric inequality, it can be shown that a matchstick graph with $n$ vertices has no more than $3n-\sqrt{2\pi\sqrt{3}\cdot n}+O(1)$ edges. We improve this upper bound to $3n-c\sqrt{n-1/4}$ edges, where $c=\frac12(\sqrt{12} + \sqrt{2\pi\sqrt{3}})$. The main tool in the proof is a new upper bound for the number of edges that takes into account the number of nontriangular faces. We also find a sharp upper bound for the number of triangular faces in a matchstick graph.