摘要
火柴棒图是一种平面图，其边绘制为单位距离线段。Harborth在1981年引入了这些图，并推测n个顶点上的火柴棒图的最大边数是\(\lfloor 3n-\sqrt{12n-3}\rfloor \)。在本文中，我们对所有的\(n\ge 1\)证明了这个猜想。证明的主要几何成分是一个与L 'Huilier不等式有关的等周不等式。
1 介绍
火柴棒图是在欧几里得平面上绘制的图，每条边都是单位长度的直线段，两条边只在一个公共端点相交。这些图是由Harborth[11,12]在1981年引入的。大多数文献涉及正则火柴棍图[3,8,9,14,15,16,21,26]或几乎正则火柴棍图[18,22,23,24,25]。也有一些论文涉及更一般的方面，如枚举[20]和算法识别[1,13]。Harborth考虑了一个极值问题，即在一个匹配棒图的e条边上找到最小n个顶点，或者等价地说，给定顶点数的最大边数。他在[12]中推测了这一点(参见[4，第225页])，并在便士图的特殊情况下用顶点数的整齐归纳法[10]证明了这一点(参见[19，定理13.12])。便士图是一种火柴棍图，其附加属性是围绕顶点的半径为1/2的圆不重叠。
定理1.1
(Harborth[10])设G为n个顶点上的火柴图，任意两个顶点之间的距离至少为1。那么G的边数满足。
对于每一个都有n个顶点和最优边的三角形格上的例子[10,19]。一般来说，证明哈伯斯的猜想更加棘手。利用等周不等式(引理1.3)，我们在[17]中证明，其中
这就隐含了对于某些小n值的Harborth猜想。本文完全地解决了这个猜想。
定理1.2
设G是一个有n个顶点和e条边的火柴图。然后。
与我们之前的论文[17]一样，作为第一步，我们使用欧拉公式和等周不等式[2]。
引理1.3
(等长不等式)对于任何周长为b，面积为A的简单多边形，我们有。
然而，我们接下来将利用一个不同的等周不等式，它考虑到G的外边界上的许多边位于同一个三角形晶格上。平面上等距不等式的一种变体，称为L 'Huilier不等式，指出在给定周长的所有多边形中，其边被约束于给定的一组方向平行，其中面积最大的多边形被限定为圆[6，第9-10页]，[7，第12-13页]。特别地，在给定周长且每条边平行于固定正六边形的一条边的所有封闭多边形中，正六边形是最优的。我们证明了这种特殊情况的以下变体，在这种情况下，我们允许周长的某一有界量在方向上不受约束。
引理1.4
设P是一个简单的多边形，其周长为b，面积为a，其总长度不平行于某个固定正六边形的任何边。然后
我们对定理1.2的证明有一种分析的味道，其中出现了许多相当弱的不等式，其中的常数可以很容易地改进。令人惊讶的是，事实证明这是不必要的。不等式通常也需要n很大，这就产生了一个潜在的问题，即这种方法只适用于足够大的n。然而，原始的等周不等式允许我们在证明的早期忽略所有的值。接下来的证明就完成了，尽管还有很多不等式需要检验。这可以手工完成，也可以通过Wolfram Alpha或Desmos等应用程序完成。为了使不等式对小n有效，我们必须平衡常数项的渐近性。很奇怪的是，这种方法能使归纳成功适用于所有的n值。
1.1 证明大纲
定理1.2的证明在第二节中。这里我们给出一个高层次的总结。证明是通过归纳法，归纳法步骤分为12个声明。由于定理1.2的情况很容易检验，我们假设和定理对所有较小的n值都成立，但对n不成立，目的是找到一个矛盾。
首先，我们表明图的最小度为3(索赔2.1)，并且是2连通的(索赔2.2)。然后，我们应用欧拉公式并对相关边-面对进行计数，以n为单位给出G边界长度的上界和非三角形内面数量的一定加权计数F(要求2.3)，以及三角形数量的下界(要求2.4)。如果这个加权计数F等于0或1，那么要么所有的内面都是三角形，在这种情况下，定理1.1适用，或者也有一个四边形，这种情况可以通过在四边形上分割图形并应用归纳法轻松处理。因此我们可以假设(权利要求2.5)。
我们将等距不等式(引理1.3)应用于G的边界长度的上界和由三角形数量的下界导出的面积的下界。这给出了F的上界形式(我们使用，但c可以小到1/20)，并表明我们可以假设其他情况(声明2.6)。
接下来我们考虑所谓的图的晶格分量，我们将其定义为每个位于某个三角晶格上的最大2连通子图。我们找到了它们的边界长度的下界(权利要求2.7)，并表明它们几乎覆盖了所有G，没有太多的重叠(权利要求2.8)。这使我们能够证明，最大的晶格分量，必须非常大(我们在声明2.9中证明了这一点，但如果n足够大，则有可能达到0.97n)。
我们将G分成和稍微扩大，并应用归纳法来获得F关于n和(声明2.10)的下界，这对证明的最后部分至关重要。我们还限定了不在(Claim 2.11)边界上的G边界上的边的数量。因此，除了一个有界的量外，G的边界边都在同一个三角格上。我们的新等周不等式(引理1.4)给出了G的面积的改进上界，它可以使用声明2.4中三角形数量的上界从下下界。这样做的结果是，我们找到了F(主张2.12)的一个很好的上界，它与主张2.10的下界一起给了我们最后的矛盾。
1.2 定义
我们定义三角形晶格是等距平面的任意子集，我们说一个有限点集位于三角形晶格上如果它是某个三角形晶格的子集。我们将使用下面的简单观察。
引理1.5
如果a和b是三角形晶格上不同的点，c是距离a和b都为1的点，那么c位于同一个三角形晶格上。
我们使用的标准图论术语可以在[5，章节1.1-1.4,4.1,4.2]中找到。我们称平面图形G的外表面的循环边界为G的边界，其长度为G的边界长度，其边为G的边界边。
我们偶尔会用到非负的函数。因为它是严格凹的，所以对于所有的固定值它都是严格递减的。这意味着下面的不等式我们会反复使用。
引理1.6
每当，，和。
2 证明
2.1 设置归纳
设G是平面上顶点的火柴图。表示边的数量。我们用归纳法证明定理1.2。这些案件都是微不足道的。由于四个顶点上的完全图不是匹配棒图，所以情况如下。所以我们修正并假设这个定理对所有少于n个顶点的火柴图都成立。在所有有n个顶点的火柴图中，固定一个边数最大的G。我们假设
（1）并将以矛盾为目标。下面的表述2.1-2.12都有未陈述的假设:归纳假设，不等式(1)，以及在所有有n个顶点的火柴图中，G的边数最大。
2.2 基本性质
要求2.1
G的每个顶点至少有三个相邻点。
证明
假设存在一个顶点v，它最多有两个邻居，令。然后通过归纳和引理1.6，
这与(1)相矛盾。
要求2.2
G是2连通的。
证明
G必须是连通的，否则我们可以移动一个连通的分量，直到它的一个顶点与另一个顶点的距离为1，这与最大值相矛盾。如果G不是2连通的，那么G有一个切顶点。因此存在两个覆盖G的子图，它们只有一个共同的顶点。然后有，，和，我们有，和
通过归纳和引理1.6，它与(1)相矛盾。
2.3 欧拉公式和重复计算
由于G是由2.2连通的，所以它的所有面都是多边形。令b表示外表面的长度，对于每个外表面，令表示以长度为i的循环为界的内表面的数量。由于G是连通的，欧拉公式给出
（2）由于G是2连通的，通过两种方式计算入射边面对，我们得到
（3）让。那么(2)和(3)暗示
（4）由式(1)可得
要求2.3
．
2.4 利用等周不等式
我们需要三角形面数量的下一个下界，这样我们就可以估计以G为界的区域的面积，然后使用等周不等式找到b的下界，并从中找到F的第一个上界。这个上界将在稍后我们证明F的改进上界时用到(声明2.12)。
要求2.4
．
证明
利用欧拉公式(2)和假设(1)，我们得到
要求2.5
．
证明
如果，则所有的内面都是三角形的，并且由于G是2连通的，它位于单个三角形晶格上。那么G是一个便士图，哈伯斯定理1.1给出了一个矛盾。
如果，则存在一个四边形的内面，其他所有的内面都是三角形的。这个四边形的每个顶点v必须位于G的边界上，否则，所有与v相交的面都是等边三角形，这意味着四边形在v处的角度是的倍数。那么这个四边形就会有角度，我们可以在两个相对的顶点之间加上一条边，这违反了G的最大值。
我们接着分解g，因为，至少有一条四边形的边不是g的边界边，设p和q是这样一条边的端点。然后没有连接，只有两个连接的组件和。设为G的子图由p和q的顶点归纳而成。然后和只有四边形的一条边是相同的，并且覆盖g，表示和，我们有和。由于pq不在G的边界上，可得，，且G的边界长度b至少为5。那么权利要求书2.3暗示，并且
与假设(1)相矛盾。
四边形的子图和覆盖G并共享边pq
要求2.6
和。
证明
用a表示G的边界多边形的面积，边长为1的等边三角形的面积为。根据主张2.4，通过等周不等式(引理1.3)和主张2.3，我们有。在这个证明的剩余部分，我们写。这样我们就得到了不等式，或者展开后，
（5）根据声明2.3和，我们得到，因此(5)的左侧随着f的减小而减小，因此我们可以代入(5)得到
因此，或者，或者用n表示，或者，根据假设，我们得出结论，根据要求。对于索赔的第二部分，我们求解F in(5)得到
为了证明这一点，只要证明
这个不等式等价于，但是，我们已经证明了，因此我们得出结论，这证明了第二部分的主张。
2.5 晶格组件
我们将G的格分量定义为位于某个三角格上的任何极大2连通子图(至少有三个顶点)。表示G by的晶格分量。表示顶点的数量，边的数量和边界的长度。假设。请注意，没有两个格组件有共同的边，否则它们的并集将是在同一格上的一个更大的2连通图。
要求2.7
对于每一个，。
证明
在三角形晶格上，并且是2连通的，所以它的边界是一个环。的边界内，通过填充所有缺失的点阵顶点和边，构造一个新的图。根据定理1.1，，也在三角晶格上。(这里我们不能使用归纳法，因为可能有超过n个顶点。)将(4)应用于(它仍然是2连通的，并且与)，我们得到，因为具有相同的外边界。
稍后我们将需要最大的点阵分量不能太小。我们首先证明了晶格分量几乎覆盖了G的所有部分，并且没有太多的重叠。
要求2.8
．
证明
对于下界，考虑一个不属于任何格分量的G的顶点v。设s为与v相关的G的内面数，因为v至少有三个邻居(表述2.1)，给入射到v的每个内面赋1/s的电荷，因为这些面都是非三角形的，总电荷为。所有这些顶点上的总电荷计数没有被任何晶格分量覆盖的顶点的数量。因此，至少G的顶点被晶格分量所覆盖，得到。
对于上界，考虑一个顶点v属于。现在设s为G与v相关联的非三角形内面的个数，因为与v相关联的两个相邻面不可能属于不同面，在v处的任意两个面之间至少有一个非三角形面属于不同面，所以v至少与t个非三角形面相关联，其中一个可以是外面。因此。赋给v的每个非三角形内表面一个电荷，这就得到了每个v的总电荷，这正是它对v的贡献。因为，我们得到总电荷最多为。因此,。
从现在开始，我们专注于最大的晶格分量。我们首先证明它覆盖了G的相当大比例。
要求2.9
．
证明
假设这就是全部。我们将通过上下跳跃找到一个矛盾。由于没有两个有共同的边界边，这个和计算所有晶格组件边界上的边数。
对于上界，请注意，如果一条边位于某个点阵分量的边界上，则它与点阵分量外部的非三角形面相邻。这给了
（6）参见权利要求书2.3和2.6。对于下界，我们只使用声明2.7:
（7）我们将右手边的下界放宽为连续优化问题。我们有。为了以后的参考，请注意，根据权利要求2.8和2.6。特别是……对于每一个，在域上定义
对于每个函数，函数都有一个最小值。在所有这些中，固定的一个，比如m，是最小的。修理一下。根据(引理1.6)的严格凹性，在开区间(3,3n /4)内不可能有两个。如果，我们不能有一些和另一些，因为我们可以用一个等于的变量来代替它们，从而得到
因此，我们不能有任何，因为这将意味着所有其他，但和，如前所述。不能让2等于3n/4，因为。因此，必然地，。由此得出
将上述式与式(6)、式(7)合在一起，可得
再次使用权利要求书2.6，它是这样的
它在n中没有解，这是矛盾的。
下一个不等式来自于对余数应用归纳假设并稍微扩大余数。
要求2.10
．
证明
设K是连接到某个顶点的顶点的集合，设G的子图由。因为它在晶格上，我们已经知道了哈伯斯定理1.1。如果，则由于G和是连通的，则假设(1)是矛盾的。因此。让和。然后和覆盖G的所有边，因此。要从上面定界，我们将使用归纳法，但我们需要确保。我们通过从上面限定|K|来做到这一点。
G分解成并与公共顶点集K
K中的每个顶点v都属于G的某个内面而不是在晶格上，否则v周围的所有内面都在同一个晶格上，所以一定是极大值的一部分。考虑任何不位于晶格上的内表面，因此至少有一个顶点不在K中。用i表示循环边界的长度。假设这个循环上除了一个顶点以外的所有顶点都在K中，并考虑剩下的顶点v与相邻的u和w在上。由于u和w在的格上，根据引理1.5,v也在同一个格上，但在矛盾的格上。因此K的大多数顶点都属于。由于是G的一个非三角形面，我们求出它的上界
由主张2.6和2.9可知，因此K不可能是全部，因此K是G的真子集，我们可以应用归纳得到
利用假设(1)和，我们得到
（8）从边界可以得出结论。
设G不在的边界上的边界边数。
要求2.11
．
证明
边界上的每条边要么是G的外表面，要么是G的内非三角形表面。设i表示循环边界的长度。不是所有的边都在的边界上。因此，在大多数边缘上有助于的边界。如果它有或多条边在的边界上，那么根据引理1.5，它一定是一个点阵多边形，所以它一定是极大性的一部分。因此，它的大多数边都在的边界上。因此,
现在的索赔是根据索赔2.3和2.7中的不平等提出的。
2.6 一个改进的等周不等式
我们的下一个目标是以类似于权利要求2.11中的上界的形式为F找到一个更好的上界。然后将这个界限(权利要求2.12)与权利要求2.10结合起来以得到一个矛盾。申明2.12将从引理1.4中的等周不等式推导出来，我们现在重申并证明它。
引理1.4
设P是一个简单的多边形，其周长为b，面积为a，其总长度不平行于某个固定正六边形的任何边。然后
证明
设h为固定的正六边形。对于任意简单多边形路径(开或闭)Q，我们用b(Q)表示它的长度，用b(Q)表示它不平行于h的任何边的总长度。如果Q是闭多边形，我们用a (Q)表示它的面积。
我们首先用，和将P修改为凸多边形。如果在Q的边集和P的边集之间存在一个双射，使得对应的边平行且长度相同，我们就说一个简单多边形Q是P的重排。注意对于任何重排Q (P)我们有和。在所有P的重排中，面积最大的固定1。我们说它是凸的。如果它不是凸的，那么它有两个顶点p和q，使得p和q之间的边界位于凸包的内部。如果我们把这部分边界用它绕p和q的中点旋转来代替，那么我们就得到了一个新的简单多边形，它仍然是p的重排，但是面积更大。
多边形和它的限定六边形H
设H表示一个六边形，它的边与H的边平行。H的边按1到6的顺序编号。对于每一个点，设为H在第i面上的线段，使得点按周围的顺序排列。表示between和的路径，其中。注意，在三角形pqr中，余弦法则给出
因此。我们现在把这个应用到每个三角形上得到H的周长的上界用b和表示
根据六边形的等周不等式(或边与固定六边形平行的六边形的L 'Huilier不等式)，具有固定周长的六边形的面积最大化是规则的。由此得出
引理1.4。
现在，我们从上面的等周估计中得到F的改进上界，再次通过使用声明2.4中的下界从下面限定面积。
要求2.12
．
证明
如前所述，G的边界多边形的面积A至少为。如果我们把这个，以及分别由声明2.3和2.11得出的b的上界和由声明2.4得出的下界代入引理1.4，我们得到
在哪里和。假设。然后
将之展开并化简，我们得到，这与声明2.6中F的上界相矛盾。因此，给出了这个要求。
2.7 结论
现在，我们将声明2.12中对F的新估计与声明2.10结合起来，得到一个矛盾。权利要求2.12和(权利要求2.5)暗示
（9）根据索赔书2.12，
那么权利要求书2.10给出
由此得出
（10）根据权利要求2.9，并且使用它和n是整数，我们有，这意味着
与(10)一起，我们得到了这个矛盾。这样就完成了归纳法的步骤，也就完成了定理1.2的证明。