2022/06/08 by Lavollée, Jérémy, Swanepoel, Konrad J.
#52C10 (Primary) 05C10 (Secondary) #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2206.03956
A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth (1981) proposed the problem of determining whether there exists a matchstick graph in which every vertex has degree exactly 5. In 1982, Blokhuis gave a proof of non-existence. A shorter proof was found by Kurz and Pinchasi (2011) using a charging method. We combine their method with the isoperimetric inequality to show that there are Ω(√(n)) vertices in a matchstick graph on n vertices that are of degree at most 4, which is asymptotically tight.