2025/06/02 by Gehér, Panna, Pach, János, Swanepoel, Konrad +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2506.01589
A graph whose vertices are points in the plane and whose edges are noncrossing straight-line segments of unit length is called a matchstick graph. We prove two somewhat counterintuitive results concerning the maximum number of edges of such graphs in two different scenarios. First, we show that there is a constant c>0 such that every triangle-free matchstick graph on n vertices has at most 2n-c√(n) edges. This statement is not true for any c>√2. We also prove that for every r>0, there is a constant ε(r)>0 with the property that every matchstick graph on n vertices contained in a disk of radius r has at most (2-ε(r))n edges.