四色猜测的手工证明（修订稿）（八）

雷明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）                  （12—1）
注意，这里对图的亏格可是没有任何限限制的。再把完全图边与顶点的关系e＝v（v－1）/2代入（12—1）式中得
v（v－1）/2＝3v－6（1－n）
v2－7v＋12（1－n）≤0                     （12—2）
解这个一元二次不等式（12—2），得其正根是
v≤（7＋√（1＋48n））/2  （v≥3）
由于顶点数v必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞ （v≥3）     （12—3）
（12—3）式中暂用＜ ＞表示其中的数字向下取整。这就是可嵌入亏格为n的曲面上的最大完全图的顶点数。因为完全图的色数γ就等于其顶点数v，即有γ完＝v，所以又有多阶曲面上图的色数是
γ图≤＜（7＋√（1＋48n））/2＞ （v≥3）   （12—4）
（12—4）式就是赫渥特的多阶曲面上的地图着色公式，推导过程中对图的亏格是没有施加任何限制的，所以它是适用于任何亏格的图的。
2、任意图顶点平均度的界：
2、1  任意图顶点平均度的上界：
在一个完全图Ｋω中增加顶点，在保证图的亏格n和密度ω都不变的情况下，图中每增加一个顶点最多只可以增加3条边。否则，增加的边数若大于三条时，当完全图Kω又是极大图时，图中就一定会产生在该亏格曲面上的交叉边，使图的亏格增大。所以，要保证图的亏格不变时，在图中每增加一个顶点，最多可以增加的度是2×3＝6。当增加的顶点数为m时，该图的平均度则是
d平均＝（ω（ω－1）＋6m）/（ω＋m）         
＝ω（ω－1）/（ω＋m）＋6m/（ω＋m）  （12—5）
（12—5）就是任意图顶点平均度的上界（式中ω（ω－1）是完全图Kω的总度数）。当m趋于无穷大时，对（12—5）式取极限得
d平均＝6                                    （12—6）
公式（12—6）说明任何亏格、任何密度的图的平均度的上界极限都是6。
2、2  任意图顶点平均度的下界：
对于任何图，在保证图的亏格n和密度ω都不变的情况下，给图中每增一顶点最少也可以使图增加1条边，增加2度。当增加的顶点数为m时，该图的平均度则是
d平均＝（ω（ω－1）＋2m）/（ω＋m）        （12—7）
（12—7）就是任意图顶点平均度的下界（式中ω（ω－1）仍是完全图Kω的总度数）。当m趋于无穷大时，对（12—7）式取极限得
d平均＝2                                    （12—8）
公式（12—8）说明任何亏格、任何密度的图的平均度的下界极限都是2。
2、3  任意图顶点的平均度曲线：
    为了对以上的公式（12—5）、（12—6）、（12—7）、（12—8）间的关系看得更清楚，我们用公式（12—5）和（12—7）做出了不同密度的图的顶点平均度表和平均度曲线，如下（表12—1）至（表12—12）和如下图12—1。
从12个表和图12—1中可以看出：
2、3、1  任何图的顶点平均度的上界都是随着图的顶点数的增加而趋近于常数6的。
当密度ω大于等于8时，曲线是下降的，平均度上界的最大值是ω－1，平均度上界的最小值是趋近于6的；当密度等于7时，平均度的上界是恒等于6的一条水平线；当密度ω小于等于6时，曲线是上升的，平均度上界的最小值是ω－1，平均度上界的最大值则是趋近于6的。而在密度小于等于4（即是亏格为0的平面图）时，由于平面图中有四种不同密度ω的图，所以，从K1到K3，依次增加一个顶点和最大可能的边时，便依次得到了K2，K3和K4，再继续增加顶点时，平均度的上界曲线就都与密度为ω＝4的图的平均度曲线重合了。实际上，四种密度的图的平均度上界是共用一条曲线的。所以仍有亏格为0的平面图（密度从1至4）的平均度上界的最小值是ω－1，平均度上界的最大值也是趋近于6的结论。
亏格n＝0，密度ω＝1时图的平均度表（表12—1）

亏格n＝0，密度ω＝2时图的平均度表（表12—2）

亏格n＝0，密度ω＝3时图的平均度表（表12—3）

亏格n＝0，密度ω＝4时图的平均度表（表12—4）

亏格n＝1，密度ω＝5时图的平均度表（表12—5）

亏格n＝1，密度ω＝6时图的平均度表（表12—6）

亏格n＝1，密度ω＝7时图的平均度表（表12—7）

亏格n＝2，密度ω＝8时图的平均度表（表12—8）

亏格n＝3，密度ω＝9时图的平均度表（表12—9）

亏格n＝4，密度ω＝10时图的平均度表（表12—10）

亏格n＝11，密度ω＝15时图的平均度表（表十12—11）

亏格n＝23，密度ω＝20时图的平均度表（表12—12）


由于密度大于等于8的图的平均度的上界是小于等于ω－1而大于6（极限）的，但永远也不可能等于6，所以密度大于等于8的图中，至少就应有一个顶点的度既是大于等于7又小于等于ω－1的；而密度小于等于6的图的平均度的上界都是小于6（极限）的，所以密度小于等于6的图中，至少也应有一个顶点的度是小于等于5的结论。当然这个结论也包括密度是小于等于4的平面图在内了。这就是平时大家都知道的任何平面图中至少都存在一个顶点的度是小于等于5的结论。
2、3、2  任何图的顶点平均度的下界都是随着图的顶点数的增加而趋近于常数2的。
当密度ω大于等于4时，曲线是下降的，平均度下界的最大值是ω－1，平均度下界的最小值是趋近于2的；当密度等于3时，平均度是恒等于2的一条水平线；当密度ω小于等于2时，曲线是上升的，平均度下界的最大值是趋近于2的，平均度下界的最小值则是ω－1。同样也是因为给K1增加一个顶点和一条边后得到的是K2，再往后增加顶点和边时，K1和K2两个图的曲线相重合，所以密度小于等于2的两种密度的平面图的平均度下界曲线也是重合的。
2、3、3　密度大于等于1的各图顶点平均度的上界曲线和下界曲线都有共同的起点，其平均度都是ω－1，即是完全图Kω的顶点平均度。
2、3、4　对于亏格为1的K7图，其平度均度上界曲线是一条度为6的水平线。这是因为在该图中每增加一个顶点时，其增加的度数均是6，而K7图本身的平均度也是6，总的平均度仍是6，所以密度为ω＝7的图的平均度曲线是一条度为6的水平线。该水平线正好就是以上两种情况下图的上界的极限（渐近线）。其平均度上界正好等于K7图的顶点数（或密度）减去1的值，即7－1＝6；
2、3、5　对于亏格为0的K3图，其平度均度下界曲线是一条度为2的水平线。这是因为在该图中每增加一个顶点时，其增加的度数均是2，而K3图本身的平均度也是2，总的平均度仍是2，所以密度为ω＝3的图的平均度曲线是一条度为2的水平线。该水平线正好就是以上两种情况下图的下界的极限（渐近线）。其平均度下界正好等于K3图的顶点数（或密度）减去1的值，即3－1＝2；
2、4  综述：
综上所述，可以看出，对于亏格大于1的图来说，其平均度都一定是小于等于该亏格下最大完全图的顶点数减1的，但又不会小于等于2；而平面图因为存在着K1和K2这样的图，所以其平均度完全有是0和1的可能，因此，对于亏格小于等于1的图来说，其平均度则都是小于等于6的。
3、韦斯特对赫渥特地图着色公式的证明[6]：
韦斯特在他的《图论导引》一书中对赫渥特地图着色公式是这样叙述的：“如果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的完全图KC的，因为完全图KC的平均度才是等于c－1的。确切一点来说，对于任意图，应该是2e/n≤c－1）。一个图的平均度是≤c－1时，这当然能说明该图的顶点中至少有一个顶点的度是等于小于c－1的。但至于为什么图中至少有一个顶点的度是小于等于c－1时，赫渥特地图着色公式就能适用，该公式就是正确的，可他并没有任何的说法。更没有说为什么平面图因存在着平均度是大于等于c－1的图（即存在着所有顶点都不小于c－1的图，如正八面体和正二十面体等。正八面体的所有顶点都是4度的，正二十面体的所有顶点都是5度的，平均度都大于K4图的c－1＝4－1＝3。），赫渥特地图着色公式就又不适用了，又是错误的呢。而只说了“由于χ（G）≤c对顶点数最多为c的任意图均成立，故只需考虑n（G）＞c的情况。”然后，就推导出了2e/n＝c－1。然而，这个2e/n＝c－1又与n（G）＞c时，χ（G）≤＜（7＋√（1＋48γ））/2＞的是否成立有什么关系呢。所以，我认为韦斯特的这个证明是不科学的。赫渥特的地图着色公式本来是可以经过严密的数学推导而得来的，是不需要再进行证明都是正确的。严密的数学推导过程就是证明的过程。
韦斯特在未证明之前就已排除了亏格为0的平面图，他说“如果G可以嵌入到Sγ（γ＞0）上，……”这也是不合适的。这就等于说，他根本就没有证明赫渥特地图着色公式为什么不适用于亏格为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  赫渥特地图着色公式本来的结果是任意亏格的图的最大团的顶点数，或者说是任意图的最小完全同态的顶点数。根据哈德维格尔的猜想，一个色数是γ的图，一定能同化成为Kγ的完全图，Kγ也就是该图的最小完全同态。这个Kγ的亏格一定是小于等于原图的亏格的（如一个奇轮的色数是4，它一定可以同化成K4的，亏格仍是0；而K3，3的亏格是1，色数是2，同化后则是K2，亏格是0，比原图的亏格1小）。不可能有平面图同化的结果是K5的，因为K5是非平面图，所以也不可能有色数是大于等于5的平面图。这也能说明四色猜测是正确的。如果某图同化后的最小完全同态是K5时，则也就说明了这个图一定不是平面图。
4、3  的确，把亏格等于0代入赫渥特的地图着色公式中，所得结果，正好就有平面图的色数是小于等于4的。这就是四色猜测。
    这也就证明了赫渥特多阶曲面上的地图着色公式对于亏格为0 的平面图同样也是适用的。

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

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

编  后  记

我在一九九二年参加陕西省数学会在西安空军工程学院（今西安空军工程大学）召开的学会第七次代表大会和学术年会时，曾对赫渥特图的4—着色作了学术论文报告，结束了自一八九○年提出的赫渥特图一直不能4—着色的历史。但这只是对一个具体图的着色，只是个别的，并不能代表全体的平面图。以前的1890年有赫渥特图的出现，今后就可能还会有其他图的出现（果然在1992年就有敢峰—米勒图的出现）。要是这样的话，什么时候四色猜测才能得到证明是正确还是不正确呢，这样的过程是不可能完结的。所以我在报告的最后提出了“不画图、不着色”对四色猜测进行证明的设想，得到了与会一些专家和学者的赞许和支持。我的这一目标，经过了从1992年至今二十五年的精心研究，现在已经实现了。在我的这个小册子里多数的证明方法就是“不画图、不着色”的，而是直接用公式进行严密的数学推导而进行证明的。另外，任何一个问题的解决，绝对不可能是只有一种方法，而是有多种方法的。从不同的角度出发都是可以解决的。我的这个小册子里的内容也体现了这一点。
四色猜测是可以用手工进行证明的，不需要计算机辅助也是可以证明。

作者：雷  明
二○一七年五月五日于长安

参  考  文  献

[1]  许寿椿著，〈图说四色问题〉，北京大学出版社，2008年1月第1版第1次印刷，第65页和106页；
[2]  张彧典，《四色问题探秘》，科学出版社，2010年10月第1版第1次印刷，第42页；
[3]  徐俊杰，《数学四色问题证明》，西北工业大学出版社，2012年3月第1版第1次印刷，第12页；
[4]  G•沙特朗等著，《图论导引》，范益政等翻译，人民邮电出版社，2007年9月第1版第1次印刷，244页；
[5]  F•哈拉里著，《图论》，李慰萱翻译，上海科学技术出版社，1980年1月第1版第1次印刷，第165页；
[6]  B•韦斯特，《图论导引》（原书第2版），李建中、骆吉洲翻译，机械工业出版社，2006年2月第1版第1次印刷，第214页。


雷  明
二○一七年四月三十日汇编于长安

注：此小册子已于二○一七年五月一日曾以《四色猜测是可以手工证明的》为题在《中国博士网》上发表过，网址是：
  
（全文完）

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，