A tight bound for the number of edges of matchstick graphs
share
A matchstick graph is a plane graph with edges drawn as unit-distance line segments. Harborth introduced these graphs in 1986 and conjectured that the maximum number of edges for a matchstick graph on n vertices is ⌊ 3n-√(12n-3)⌋. In this paper we prove this conjecture for all n≥ 1. The main geometric ingredient of the proof is an isoperimetric inequality related to Lhuilier's inequality.
READ FULL TEXT