2021/08/17 by Jérémy Lavollée, Lavollée, Jérémy, Konrad J. Swanepoel +1
Computer Science · Mathematics · #05C10 (Secondary) #52C10 (Primary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2108.07522
openalex publication_date 2021/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We show that a matchstick graph with n vertices has no more than 3n-c√(n-1/4) edges, where c=\frac12(√(12) + √(2π√(3))). The main tools in the proof are the Euler formula, the isoperimetric inequality, and an upper bound for the number of edges in terms of n and the number of non-triangular faces. We also find a sharp upper bound for the number of triangular faces in a matchstick graph.