Bounding the number of edges of matchstick graphs

Abstract

We show that a matchstick graph with $n$ vertices has no more than $3n-c\sqrt{n-1/4}$ edges, where $c=\frac{1}{2}(\sqrt{12}+\sqrt{2\pi \sqrt{3}})$. The main tools in the proof are the Euler formula, the isoperimetric inequality, and an upper bound for the number of edges in terms of $n$ and the number of non-triangular faces. We also find a sharp upper bound for the number of triangular faces in a matchstick graph.

arXiv comment9 pages, 3 figures