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 $\Omega(\sqrt{n})$ vertices in a matchstick graph on $n$ vertices that are of degree at most $4$, which is asymptotically tight.
翻译:火柴图是飞机上的无跨线单位距离图。 港( 1981年) 提出了确定是否有每顶脊椎都具有5美元的火柴图的问题。 1982年, Blokhuis 提供了不存在的证据 。 Kurz 和 Pinchasi (2011年) 使用电荷方法发现了一个较短的证据 。 我们结合了它们的方法和等离线性不平等, 以显示在1美元顶峰的火柴图上存在$\Omega(\\ sqrt{n}) $( $) 的脊椎, 其程度最多为$4美元, 且微乎乎其微。