2022/09/20 by Lavollée, Jérémy, Swanepoel, Konrad · 2 citations
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Primary 52C10. Secondary 05C10
paper · doi:10.48550/arxiv.2209.09800
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 \lfloor 3n-√(12n-3) \rfloor. 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.