证明四色猜测的其他四种方法

雷明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时，新增加的顶点，可以在图中的一个面内，也可以在图的一条边上，只要在图不变成非平面图的情况下，尽可能多的使该顶点与图中的其他顶点相邻，最后都可以成为一个极大图：若该顶点处在图的一个面内时，它只能与三个顶点相邻，它还有除三个顶点所着颜色以外的第四种颜色可着；若该顶点处在图的一条边上时，它也只能与四个顶点相邻，按照坎泊1879的证明，这个顶点一定是能着上四种颜色之一的。这就证明了v＝5时的极大图也是可4—着色的，其色数γ＝4≯4。
    从图1中还可以看出，不管增加的顶点是增加在何处，图中都是因增加了1个顶点而增加了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、用还原法进行证明
由于平面图中一定存在着度小于等于5的顶点，若把这些顶点从图中去掉时，图仍然还是一个平面图，但同时又会产生新的度小于等于5的顶点。再把新生成的度小于等于5的顶点去掉时，又产生新的度小于等于5的顶点。就这样一直的把度小于等于5的顶点“去掉”下去，图最后将成为一个顶点数为1的K1图，只用一种颜色就够了。
现在再按“去点”时的相反方向往回走，即还原。先把最后一次去掉的那个度小于等于5的顶点还原上去，图中就有两个顶点，这时一定是K2图，两种颜色也就够用了；再把最后第二次去掉的那个度小于等于5的顶点还原上去，图中就有3个顶点了，最多三种颜色就够用了（因为这时图可能是一条道路，只需用两种颜色；也可能是一个3—圈即K3图，就得用三种颜色，所以说最多三种颜色就够用了）；第三步再把最后第三次去掉的那个度小于等于5的顶点还原上去，图中就有4个顶点了，同样，最多四种颜色也就够用了；若按次序再还原上去一个顶点时，这时图中就有5个顶点了，但这第5个顶点与前4个顶点的相邻关系可能是：
①　前4 个顶点间没有构成密度是4的K4团时，这四个顶点最多只占用三种颜色，第5个顶点虽然可以与前4个顶点均相邻，但至少仍有一种颜色可以着上，图的色数仍没有大于4；
②　前4个顶点若构成了密度是4的K4团时，这四个顶点就占用完了四种颜色，但第5个顶点最多却只能与前4个顶点的3个顶点相邻（否则图将成为非平面图，会出现在顶点之外边与边的相交叉的情况），这时，第5个顶点仍有一种颜色可以着上，图的色数仍没有大于4。
按次序再还原第6个顶点时，与第5个顶点还原时相同，该顶点最多也只可能与图中的K4团有3个顶点相邻，或者在前5个顶点构成的图的密度小于4时，都至少还有一种颜色可以着上；
以后再按次序还原上去其他的顶点，与已还原过的顶点的相邻关系，也都只能是以上的两种情况，所还原的顶点均可着以图中已用过的四种颜色之一。一直到把原图中的所有顶点都还原完毕，图中都不会出现使用四种颜色以外的第五种颜色的情况。这也就证明了四色猜测是正确的。
4、用断链法进行证明
一个构形的待着色顶点，如果其围栏顶点占用的颜色数未达到4时，该待着色顶点都是可以着上四种颜色之一的；如果围栏顶点已占用完了四种颜色，则必须想办法从围栏顶点中空出一种颜色来，然后给待着色顶点着上。如何空出颜色，这就得灵活的运用坎泊的颜色交换技术了。
用坎泊的颜色交换技术，空出颜色来给待着色顶点的原则是：首先要看，在以待着色顶点为中心顶点的轮中，对角顶点间的颜色所构成的色链是不是连通链，如果是不连通的链时，才可以进行交换，也才能空出颜色给待着色顶点。而如果是连通链时，即就是交换了这种链也是空不出颜色来的。
4—轮构形中只可能有一条连通链，该构形一定是可以通过坎泊的颜色交换，空出一种颜色给待着色顶点着上的。而5—轮构形的情形就不同了，其中有可能有两条连通链的可能。若两链只有一个共同的起点，或是只有一个交叉顶点时，也一定是可以通过坎泊交换空出颜色来给待着色顶点的。而只有当两条连通链既有共同的起点，又有交叉顶点时，则难以通过交换5—轮对角链的办法解决问题。这种情况怎么办？可以想到，既然不连通的链是可以交换的，那么是否可以把已连通的链变成不连通的呢？完全可以。没有了连通链，或者只有一条连通链，一定是可以通过交换空出颜色给待着色顶点的。这种方法我们叫做“断链法”。
断链方法的原理是：用四种颜色A、B、C、D所能构成的链有六种，即A—B、A—C，A—D，B—C，B—D和C—D六种，如果有A—B链是连通的时，则该链中的A和B在该链以外，只能与C和D相邻，构成A—C链和A—D链或者B—C链和B—D链，从A—B链上的任何一个A或B顶点起，开始交换上述的A—C链或A—D链（或者B—C链或B—D链）中的一种，都可以使A—B链上的被交换的顶点A或顶点B变成C或D，使A—B链断开。这样就可以对5—轮轮沿中的顶点A或B施行A—B链的交换，空出A或B来给待着色的5—轮中心顶点着上。
我们在对赫渥特图，敢峰—米勒图的着色中，使用的就是这种方法。可以说任何平面图中的任何链都是可以通过这一方法“断开”的。连通链断开了，就可以通过施行坎泊的颜色交换技术，空出已用过的四种颜色之一，给待着色顶点着上。所以也就可以说，任何平面图着色时是不会用到第五种颜色的。这也就证明了四色猜测是正确的。

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

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

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，，

雷明85639720

,,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，