三十多年研究四色问题的总结：《四色猜测的手工证明》（四）

雷明85639720

三十多年研究四色问题的总结：《四色猜测的手工证明——证明四色猜测的十多种方法汇总》（四）
雷  明
二○一七年四月三十日于西安

（接上一贴）


证明四色猜测的其他三种方法
雷  明
（二○一七年元月三十一日）

1、用反证法进行证明
五色地图就是需要用五种颜色着色的地图，最小五色地图就是地图中只有五个区域，且每两个区域都是相邻的地图。按坎泊的想法，如果不存在五色地图时，则地图四色猜测就是正确的。
现在我们假设这种五色地图存在，则一定也存在最小的五色地图。由于最小五色地图中每一个区域都与其他的四个区域相邻，所以每个区域就有四条边界线，五个区域共有二十条边界线，但每条边界都是两个区域所共有，所以该最小五色地图实际只有十条边界线（即图的边数e＝10）。又由于地图是一个3—正则图，所以有3v（顶点数）＝2e（边数）的关系。把最小五色地图的边数e＝10代入3v＝2e中，得到顶点数v＝20/3，不是整数，这是不符合实际情况的，应该否定假设。说明我们假设的最小五色地图是不存在的。
按坎泊的想法，这也就证明了地图四色猜测是正确的。同样的，平面图的四色猜测也是正确的。四色猜测正确。
2、用数学归纳法进行证明
用v表示图的顶点数，e表示图的边数，f是图的面数，γ表示图的色数。
当v＝1时，一种颜色就够用了，γ＝1＜4；
当v＝2时，两种颜色也就够用了，γ＝2＜4；
当v＝3时，边数最多时是K3图，是一个极大图，也是一个完全图，两两顶点均相邻，必须用三种颜色着色，γ＝3＜4；
当v＝4时，新增加的这第4个顶点，只有位于上面的K3图的一个面内时，最多可以增加3条边，使K3成为一个极大图K4，也是一个完全图，两两顶点也均相邻，着色时四种颜色也就够用了，γ＝4≯4；

当v＝5时，新增加的顶点，可以在图中的一个面内，也可以在图的一条边上，只要在图不变成非平面图的情况下，尽可能多的使该顶点与图中的其他顶点都相邻，最后都可以成为一个极大图：若该顶点处在图的一个面内时，它只能与三个顶点相邻（如图1，a），还有除了三个顶点所着颜色以外的第四种颜色可着；若该顶点是处在图中的一条边上时，它也只能与四个顶点相邻（如图1，b和图1，c），按照坎泊1879的证明，这个顶点一定是能着上四种颜色之一的。这就证明了v＝5时的极大图也是可4—着色的，其色数γ＝4≯4。
从图1中还可以看出，不管增加的顶点是增加在何处，图中都是因增加了1个顶点而增加了3条边和两个面。若再在图中增加顶点，仍是增加一个顶点最多增加3条边和两个面时，图都不会变成非平面图，且所得到的图一定都是极大图，就一定都是可4—着色的，色数都是γ＝4≯4；
当v＝k时，这个极大图当然也是可4—着色的，色数仍是γ＝4≯4。已知在极大图中都有e＝3v－6和f＝2v－4的关系，所以这里也应有e＝3k－6和f＝2k－4的关系；当v＝k＋1时，按上面的证明和分折，所增加的这一个顶点不但是可以着上图中已用过的四种颜色之一的，而且图中也因增加了这一个顶点而增加了三条边和两个面，使得图的边数和面数分别变成了e＋3和f＋2。代入上两式得：e＋3＝3（k＋1）－6和f＋2＝2（k＋1）－4，化简后仍有e＝3k－6和f＝2k－4的关系，所以图仍是一个极大的平面图。
到此就证明了任何极大图都是可4—着色的。因为在相同顶点数的平面图中，极大图的边数是最多的，所以边数比极大图少的任意平面图的色数也一定是不会大于4的。这也就证明了四色猜测是正确的。
3、用断链法进行证明
一个构形的待着色顶点，如果其围栏顶点占用的颜色数未达到4时，该待着色顶点都是可以着上四种颜色之一的；如果围栏顶点已占用完了四种颜色，则必须想办法从围栏顶点中空出一种颜色来，然后给待着色顶点着上。如何空出颜色，这就得灵活的运用坎泊的颜色交换技术了。
用坎泊的颜色交换技术，空出颜色来给待着色顶点的原则是：首先要看，在以待着色顶点为中心顶点的轮中，对角顶点间的颜色所构成的色链是不是连通链，如果是不连通的链时，才可以进行交换，也才能空出颜色给待着色顶点。而如果是连通链时，即就是交换了这种链也是空不出颜色来的。
4—轮构形中只可能有一条连通链，该构形一定是可以通过坎泊的颜色交换，空出一种颜色给待着色顶点着上的。而5—轮构形的情形就不同了，其中有可能有两条连通链的情况。若两链只有一个共同的起点，或是只有一个交叉顶点时，也一定是可以通过坎泊的颜色交换，空出颜色来给待着色顶点的。而只有当两条连通链既有共同的起点，中途又有交叉顶点时，则难以通过交换5—轮对角链的办法解决问题。这种情况怎么办？可以想到，既然不连通的链是可以交换的，那么是否可以把已连通的链变成不连通的呢？完全可以。没有了连通链，或者只有一条连通链，一定是可以通过交换空出颜色给待着色顶点的。这种方法我们叫做“断链法”。
断链方法的原理是：用四种颜色A、B、C、D所能构成的链有六种，即A—B、A—C，A—D，B—C，B—D和C—D六种。如果在5—轮轮沿顶点（即围栏顶点）外有A—C链是连通的时，则该链中的A色和C色的顶点在该链以外，只能与B色和D色的顶点相邻，构成A—B链和A—D链或者C—B链和C—D链。从A—C链上的任何一个A色或C色的顶点起，开始交换上述的A—B链或A—D链（或者C—B链或C—D链）中的一种，都可以使A—C链上开始交换的A色顶点或C色顶点变成B色或D色，使A—C链断开。这一步就是“断链的交换”，只能断链，但不能空出颜色，只能为下一步空出颜色的交换，作好技术上的条件准备。 A—B链已经断开了，成了不连通的链，这样就可以对5—轮轮沿中的A色顶点或C色顶点施行A—C链的空出颜色的交换，空出A或C来给待着色的5—轮中心顶点着上。
我们在对赫渥特图和敢峰—米勒图的着色中，使用的就是这种方法。可以说任何平面图中的任何链都是可以通过这一方法“断开”的。连通链断开了，就可以通过施行坎泊的空出颜色的交换技术，空出已用过的四种颜色之一，给待着色顶点着上。所以也就可以说，任何平面图着色时是不会用到第五种颜色的。这也就证明了四色猜测是正确的。


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


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


赫渥特地图着色公式也适用于亏格为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）
公式（6）说明任何亏格、任何密度的图的平均度的上界极限都是6。
2、2  任意图顶点平均度的下界
对于任何图，在保证图的亏格n和密度ω都不变的情况下，给图中每增一顶点最少也可以使图增加1条边，增加2度。当增加的顶点数为m时，该图的平均度则是
d平均＝（ω（ω－1）＋2m）/（ω＋m）            （7）
（7）就是任意图顶点平均度的下界（式中ω（ω－1）仍是完全图Kω的总度数）。当m趋于无穷大时，对（7）式取极限得
d平均＝2                                       （8）
公式（8）说明任何亏格、任何密度的图的平均度的下界极限都是2。
2、3        任意图顶点平均度曲线
    为了对以上的公式（5）、（6）、（7）、（8）间的关系看得更清楚，我们用公式（5）和（7）做出了不同密度的图的顶点平均度表和平均度曲线，如下（表一）至（表十二）和如下图1。（说明：由于图发上来时变形较大，所以就不发图了。）
从表和图1中可以看出：
①  任何图的顶点平均度的上界都是随着图的顶点数的增加而趋近于常数6的。
当密度ω大于等于8时，曲线是下降的，平均度上界的最大值是ω－1，平均度上界的最小值是趋近于6的；当密度等于7时，平均度的上界是恒等于6的一条水平线；当密度ω小于等于6时，曲线是上升的，平均度上界的最小值是ω－1，平均度上界的最大值则是趋近于6的。而在密度小于等4（即是亏格为0的平面图）时，由于平面图中有四种不同密度ω的图，从K1到K3，依次增加一个顶点和最大可能的边时，便依次得到了K2，K3和K4，再继续增加顶点时，平均度的上界曲线就都与密度为ω＝4的图的平均度曲线重合了。实际上，四种密度的图的平均度上界是共用一条曲线的。所以仍有亏格为0的平面图（密度从1至4）的平均度上界的最小值是ω－1，平均度上界的最大值也是趋近于6的结论。

由于密度大于等于8的图的平均度的上界是小于等于ω－1而大于6（极限）的，但永远也不可能等于6，所以密度大于等于8的图中，至少就应有一个顶点的度既大于等于7又小于等于ω－1的；而密度小于等于6的图的平均度的上界都是小于6（极限）的，所以密度小于等于6的图中，至少也应有一个顶点的度是小于等于5的结论。当然这个结论也包括密度是小于等于4的平面图在内了。这就是平时大家都知道的任何平面图中至少都存在一个顶点的度是小于等于5的结论。
②  任何图的顶点平均度的下界都是随着图的顶点数的增加而趋近于常数2的。
当密度ω大于等于4时，曲线是下降的，平均度下界的最大值是ω－1，平均度下界的最小值是趋近于2的；当密度等于3时，平均度是恒等于2的一条水平线；当密度ω小于等于2时，曲线是上升的，平均度下界的最大值是趋近于2的，平均度下界的最小值则是ω－1。同样也是因为K1增加顶点和边后得到的是K2，再往后增加顶点和边时，两个图的曲线相重合，所以密度小于等于2的两类平面的图平均度下界曲线也是重合的。
③　密度大于等于1的各图顶点平均度的上界曲线和下界曲线都有共同的起点，其平均度都是ω－1，即是完全图Kω的顶点平均度。
④　对于亏格为1的K7图，其平度均度上界曲线是一条度为6的水平线。这是因为在该图中每增加一个顶点时，其增加的度数均是6，而K7图本身的平均度也是6，总的平均度仍是6，所以密度为ω＝7的图的平均度曲线是一条度为6的水平线。该水平线正好就是以上两种情况下图的上界的极限（渐近线）。其平均度上界正好等于K7图的顶点数（或密度）减去1的值，即7－1＝6；
⑤　对于亏格为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、韦斯特对赫渥特地图着色公式的证明
韦斯特在他的《图论导引》一书中对赫渥特地图着色公式是这样叙述的：“如果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的色数是2，同化后则是K2，亏格是0，比原图的亏格1小）。不可能有平面图同化的结果是K5的，因为K5是非平面图，所以也不可能有色数是大于等于5的平面图。这也能说明四色猜测是正确的。如果某图同化后的最小完全同态是K5时，则也就说明了这个图一定不是平面图。
4、3  的确，把亏格等于0代入赫渥特的地图着色公式中，所得结果，正好就有平面图的色数是小于等于4的。这就是四色猜测。
    这也就证明了赫渥特多阶曲面上的地图着色公式对于亏格为0 的平面图同样也是适用的。




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



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



编  后  记

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



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

注：此小册子已于二○一七年五月一日在《中国博士网》上发表过，网址是：
   
（完）

  

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,