A tight bound for the number of edges of matchstick graphs
Lavollée, J. & Swanepoel, K.
(2024).
A tight bound for the number of edges of matchstick graphs.
Discrete and Computational Geometry,
72(4), 1530 - 1544.
https://doi.org/10.1007/s00454-023-00530-z
(2024).
A tight bound for the number of edges of matchstick graphs.
Discrete and Computational Geometry,
72(4), 1530 - 1544.
https://doi.org/10.1007/s00454-023-00530-z
A matchstick graph is a plane graph with edges drawn as unit-distance line segments. Harborth introduced these graphs in 1981 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 L’Huilier’s inequality.
