赫渥特地图着色公式也适用于亏格为0的平面图

雷明85639720

赫渥特地图着色公式也适用于亏格为0的平面图
雷  明
（二○一七年二月一日）

1、用赫渥特地图着色公式的推导
顶点数v≥3的图都有3f≤2e（f是面数，e是边数）的关系，把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2（1－n）（n是图的亏格）中得
    e≤3v－6（1－n）（v≥3）                     （1）
注意，这里对图的亏格可是没有任何限限制的。再把完全图边与顶点的关系e＝v（v－1）/2代入（1）式中得
v（v－1）/2＝3v－6（1－n）
v2－7v＋12（1－n）≤0                         （2）
解这个一元二次不等式（2），得其正根是
v≤（7＋√（1＋48n））/2  （v≥3）
由于顶点数v必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞ （v≥3）        （3）
（3）式中暂用＜ ＞表示其中的数字向下取整。这就是可嵌入亏格为n的曲面上的最大完全图的顶点数。因为完全图的色数γ就等于其顶点数v，即有γ完＝v，所以又有多阶曲面上图的色数是
γ图≤＜（7＋√（1＋48n））/2＞ （v≥3）      （4）
（4）式就是赫渥特的多阶曲面上的地图着色公式，推导过程中对图的亏格是没有施加任何限制的，所以它是适用于任何亏格的图的。
2、图顶点平均度的界
2、1  任意图顶点平均度的上界
在一个完全图Ｋω中增加顶点，在保证图的亏格n和密度ω都不变的情况下，图中每增加一个顶点最多只可以增加3条边。否则，增加的边数若大于三条时，当完全图Kω又是极大图时，图中就一定会产生交叉边，使图的亏格增大。所以，要保证图的亏格不变时，在图中增加一个顶点，最多可以增加的度是2×3＝6。当增加的顶点数为m时，该图的平均度则是
d平均＝（ω（ω－1）＋6m）/(ω＋m)＝ω（ω－1）/(ω＋m)＋6m/(ω＋m)                 （5）
（5）就是任意图顶点平均度的上界（式中ω（ω－1）是完全图Kω的总度数）。当m趋于无穷大时，对（5）式取极限得
d平均＝6     （6）
公式（2）说明任何亏格、任何密度的图的平均度的上界极限都是6。在亏格n为各种值时，从该亏格下最大完全图的顶点数起，根据（5）式用顶点数v的变化对平均度作图，得到如图1所示的多条曲线。
①  图的亏格大于1、最大团的顶点数v大于7的图来说，其平均度是一个减函数。因为在相同顶点数的图中，完全图的边数是最多的，平均度也是最大的，所以在保证图密度和亏格都不变时，给图的面中每增加一个顶点最多所增加的三条边所产生的度最多也只是6度，是小于顶点数大于7的完全图的平均度v－1的（由于v大于7，所以v－1是大于6的）。只是当图的顶点数趋近于无穷大时，它的下极限是6，所以它是一个减函数。其平均度d平均是处在6＜d平均≤v－1（v＞7）之间的。这里的6是亏格大于1时不同亏格的图的平均度上界的下极限，这时的平均度是决不会减小到6的。其平均度的最大值（即上界的上线）就是该亏格下最大完全图的顶点数（也即最大完全图的密度）减1（即ω－1）。因此亏格大于1的图中至少存在着一个顶点的度是小于等于该亏格下的最大完全图的顶点数（或密度）减1的；

②  对于亏格小于等于1、最大团顶点数v小于7的图来说，其平均度则是一个增函数。在保证图密度和亏格都不变时，给图的面中每增加一个顶点，最多只能增加三条边，最多只能产生6度，是大于顶点数小于等于6的完全图的平均度v－1的（由于v小于等于6，所以v－1是小于等于5的）。当图的顶点数趋近于无穷大时，它的上极限也是6，是一个增函数。其平均度d平均是处在v－1≤d平均＜6（v≤6）之间的。这里的6是亏格为0时图的平均度上界的上极限，这时的平均度也是决不会达到6的。其平均度的最小值（即上界的下线）就是该亏格下各完全图的顶点数（或密度）减1（也即ω－1）。
③  对于亏格为1的K7图，其平度均度曲线却是一条度为6的水平线。这是因为在该图中增加一个顶点时，其增加的度数均是6，而K7图本身的平均度也是6，总的平均度仍是6，所以密度为ω＝7的图的平均度曲线是一条度为6的水平线。该水平线正好就是以上两种情况下图的上界的极限（渐近线）。其平均度正好等于K7图的顶点数（或密度）减去1的值，即7－1＝6；
2、2  任意图顶点平均度的下界
对于任何图，在保证图的亏格n和密度ω都不变的情况下，给图中每增一顶点最少也可以使图增加1条边，增加2度。当增加的顶点数为m时，该图的平均度也是前面的公式（5）和（6），其平均度下界的极限都是常数2，但其平均度最小也不可能达到2。其下界的曲线也是从各亏格下的最大完全图的平均度开始，趋近渐近线2（度为2的水平线）为止的多条曲线。为了图面清析，所以图1中没有把平均度的下界曲线画出来，只画了平均度下界的极限（渐近线）。
2、3  综上所述，可以看出，对于亏格大于1的图来说，其平均度都一定是小于等于该亏格下最大完全图的顶点数减1的，但又不会等于小于2；而平面图因为存在着K1和K2这样的图，所以其平均度完全有是0和1的可能，因此，对于亏格小于等于1的图来说，其平均度则都是小于等于6的。
3、韦斯特对赫渥特地图着色公式的证明
韦斯特在他的《图论导引》一书中对赫渥特地图着色公式是这样叙述的：“如果G可以嵌入到Sγ（γ＞0）上，则χ（G）≤＜（7＋√（1＋48γ））/2＞（这里我用＜ ＞来代替其中的数字向下取整——雷明注）。他在证明时则说：“令c＝（7＋√（1＋48γ））/2。只要证明了能够嵌入Sγ上的任意任意简单图有一个顶点的度至多为c－1，就可以通过对n（G）用数学归纳法得出χ（G）的这个界。”他这里的γ是曲面S的亏格，n是图的顶点数。
可韦斯特证来证去，只得出了一个2e/n＝c－1的结论。因为2e（e是图的边数）是图的总度数，那么2e/n就是图的平均度了。一个图的平均度是c－1时，这当然能说明图的顶点中至少有一个顶点的度是等于小于c－1的。但至于为什么图中只有一个顶点的度是小于等于c－1时，就能说明赫渥特的地图着色公式是正确的，可他并没有说。而只说了“由于χ（G）≤c对顶点数最多为c的任意图均成立，故只需考虑n（G）＞c的情况。”然后，他推导出了2e/n＝c－1，这又与n（G）＞c时，χ（G）≤＜（7＋√（1＋48γ））/2＞成立不成立有什么关系呢。所以，我认为这个证明是不对的。这个公式本来是可以以过严密的数学推导而得来，不需要经过证明都是正确的。
韦斯特在未证明之前就已排除了亏格为0的平面图，他说“如果G可以嵌入到Sγ（γ＞0）上，……”这是不合适的。他还说“当γ＝0时，这里给出的这个关键不等式是不成立的，因此对可平面图来讲这里的论述是无效的，尽管γ＝0时公式简化为χ（G）≤4。”我不知道，不作工作怎么就能知道该公式对于亏格为0的平面图是不适合的呢。我们已经推导出了赫渥特地图着色公式，根本就不要什么附加条件。看来多数人在证明该公式时，早就把γ＝0排除在外了。
韦斯特紧接着还说：“证明Heawood的界是最优的涉及将Kn嵌入到Sγ上，其中γ＝［（n－3）（n－4）/12］。”这也是不对的。林格尔公式γ＝［（n－3）（n－4）/12］与赫渥特地图着色公式χ（G）≤＜（7＋√（1＋48γ））/2＞都是由多阶曲面上的欧拉公式v＋f－e＝2（1－n）和完全图的顶点与边的关系e＝v（v－1）/2推导出来的，而且林格尔公式与赫渥特地图着色公式是互为反函数的，从一个是可以推得另一个的。怎么能用以相互证明呢，这样不就是出现了循环论证了吗。因此，沙特朗在他的《图论导引》一书中用林格尔公式来证明赫渥特的地图着色公式也是不合适的。
现在看来，赫渥特地图着色公式当时赫渥特并不是经过严密的数学推导而得到的，公式后的附加条件（γ＞0）可能是赫渥特自已加上的，因为他对他的图——赫渥特图并没有能够进行4—着色，而且这个图又是一个平面图，所以他只好在他的公式后增加一个（γ＞0）的附加条件。这样以来他的公式就算是完满了。可没有想到这个公式仍然是能够经过严密的数学推导而得到的。
4、赫渥特地图着色公式适用于亏格为0的平面图的证明
4、1  该公式是可以通过严密的数学推导而得来的，是不需要进行证明的。推导过程中是没有任何限制条件的，其当亏格为0时，计算结果是平面图的色数小于等于4，也是正确的，是一个正常的、必然的结果，决非偶然。
4、2  韦斯特证明的结果是亏格大于等于1的图中，都有顶点平均度小于等于c－1（c是该亏格下的最大完全图的顶点数），言外之意就是，平面图满足不了这个条件。
我们在前面论述任意图的平均度时，虽然也得出了亏格大于等于1的图的顶点平均度是小于等于c－1的，却得出了亏格小于等于1的图的顶点平均度是小于等于6的。但是，在平面图中却也只有正八面体和正二十面体所对应的图的顶点平均度是大于4－1＝3的（正八面体的平均度是4，正二十面体的平均度是5），而其他的任何平面图的平均度都是小于等于3的。现在我们只要证明这两个图的是可4—着色的，就应该说任何平面图都是可4—着色的，赫渥特的地图着色公式对于平面图来说也是适用的。
对于这两个非常简单的图来说，无论那个人都是可以很随便的给其进行4—着色的。这样也就正好弥补了韦斯特所说的，平面图中并不是任何图都有平均度都是小于等于（7＋√（1＋48γ））/2的缺陷，正好说明了任何平面图也都是4—可着色的。
4、3  的确，把亏格等于0代入赫渥特的地图着色公式中，所得结果，正好就是平面图的色数是小于等于4的。这就是四色猜测。


雷  明
二○一七年二月二日于长安

注：此文已于二○一七年二月二日在《中国博士网》上发表过，网址是：

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，