四色猜测的理论与实践两种证明方法 （修改稿）

雷明85639720

四色猜测的理论与实践两种证明方法
（修改稿）
雷  明
(二○二○年三月十四日)
（我在这里发不上图，请到《中国博士网》中去看）

1、理论证明的方法：
1、1  把地理问题转化成数学问题：
地图是一个无割边的3—正则的平面图，其对偶图是一个极大的平面图。给地图的面上的着色就相当于对其对偶图的顶点着色。只要证明了极大平面图的四色猜测是正确的，则地图四色猜测就是正确的了。同时，由极大平面图通过“去顶”和“减边”所得的任意平面图的色数，则只会减少而不会再增大。所以证明了极大平面图的四色猜测是正确的，则任意平面图的四色猜测也就是正确的了。这就把一个地理问题转化成了数学问题。
1、2  极大平面图的生成：
地图是3—正则的平面图，其对偶图就是所有面均是三边形面的极大平面图。面数最少的地图，如海地岛的地图，其上只有两个国家即海地和多米尼加，四周被海洋“国家”包围着。该地图中只有三个面，其对偶图就是一个K3图极大图，用“增加顶点和边”的办法从K3图开始可得到有任意顶点数的、各顶点的度也是任意大的极大平面图。这些极大平面图一定都是可4—着色的。证明如下：
1、3  极大平面图四色猜测的理论证明：
极大平平面图的生成过程是从顶点数是3的极大平面图K3开始的，K3图只用三种颜色。再在K3图的一个面内增加一个顶点和三条边，可得到一个K4图的极大平面图，该增加的顶点只能用第四种颜色（但不能在K3的边上增加顶点，因为这样增加了顶点后，是不能生成极大图的）；从K4图开始，以后再在新生成的极大平面图的任何一个面内增加一个顶点和三条边，所得到的图仍是极大平面图，则该顶点只能用与该面三个顶点不同的第四种颜色；若增加的顶点不在面内，而是在一条边上，则仍要使图保持是极大平面图时，还得要再增加两条新边，共计也是增加了三条边（因为增加的顶点是在边上，把该边已分成了两条）。增加的这个顶点一定是位于一个4—轮的中心顶点上的。根据坎泊的证明，这样的4—轮“构形”一定是可约的，即增加的这个顶点一定是可以着上图中已用过的四种颜色之一的。就这样一直不停的增加下去，就可得到顶点数是任意多的、各顶点的度是任意大的极大平面图，其所用的颜色数总是不会超过4的。这就证明了任何极大的平面图都一定是可4—着色的。
1、4  四色猜测是正确的：
极大平面图的四色猜测是正确的。那么地图的四色猜测和任意平面图的四色猜测也就是正确的了。证毕。
2、实践证明的方法：
2、1  构形：
实践的方法就是着色的方法。对任何一个极大平面图着色，最后总是要遇到一个将要着色的顶点，其周围顶点都已着上了四种颜色之一的情况。把具有这种只剩下一个顶点未着色的图就叫做“构形”，未着色的顶点叫待着色顶点，把与待着色顶点直接相邻的顶点叫围栏顶点。若与待着色顶点相邻的顶点所占用的颜色数小于等于3时，该顶点至少还是有一种颜色可着的；若与待着顶点相邻的顶点所占用的颜色数已经达到了4时，能否给这个顶点着上图中已过的四种颜色之一，这是解决四色问题的关键。
2、1  把无穷问题变成有穷问题：
图中的任何一个顶点都是可以做为待着色顶点的，由于各顶点的度都是不相同的，所以这看起来好象是一个无穷的问题。但图论中却已证明了任何平面图中一定存在着度是小于等于5的顶点。这就可以把一个看似无穷的问题，转化成一个有穷的问题了。使我们在着色时总可以把最后一个要着色的待着色顶点放在度是小于等于5的顶点上。只要研究度小于等于5的几种待着色顶点，是否可以着上图中已用过的4种颜色之一就可以了。如果这些情况下的待着色顶点，都可以着上图中已用过的4种颜色之一，则四色猜测就是正确的。
2、3  四色问题的实质是减少围栏顶点所占用的颜色数：
解决这一情况的关键问题，是要把与待着色顶点相邻的围栏顶点所占用的颜色数，由4种减少到3种。坎泊1879年已经证明了待着色顶点的度小于等于4的构形和待着色顶点的度等于5的、但可连续的移去两个同色的构形，是可以把围栏顶点所占用的颜色数由4种减少到3种的，待着色顶点一定是可以着上图中已用过的4种颜色之一的。但他却遗漏了一种在待着色顶点是5度的情况下，具有“双环交叉链”的、好象是把围栏顶点所占用的四种颜色不能减少下来的一种情况的构形。这就是1890年赫渥特构造的图。把具有这种图结构特点的图，就叫做赫渥特构形，即H—构形。今天研究四色问题时，主要就是研究对具有双环交叉链的构形的可4—着色的问题。
2、4  H—构形的不可免集：
以下的图1到图7的六个图，不但都含有双环交叉的A—C链与A—D链，同时也都可从任一个同色的顶点B交换了与其对角顶点的颜色构成的对角链后，就可新生成从另一个同色的顶点B到其对角顶点的连通链，不可能连续的移去两个同色B，是7个地地道道的H—构形。

图1到图3是三个有环形链的构形：图1是含有经过了三个围栏顶点的A—B环形链的构形；图2是含有经过了两个围栏顶点的C—D环形链的构形；图3是既含有经过了三个围栏顶点的A—B环形链，又含有经过了两个围栏顶点的C—D链的构形。图4到图7是四个不含环形链的构形：图4是不含有任何经过围栏顶点的环形链的、但A—B链和C—D链都只是一条的构形。但把图4中的某个顶点（图中的加大顶点）的颜色改变后，就可以变成图1或图2的含有经过了围栏顶点的环形链的构形（如图8和图9）。图5到图7同样也是三个不含环形链的构形，但其中的A—B链和C—D链却至少有一个至少是不连通的两段。也可以把这三图与图1或图2同样看待，给待着色顶点进行着色。

无环形链的构形可以转化成有环形链的构形，可以这样来证明：在一个无环形链的构形中，不管两条相反链A—B和C—D是如何的弯曲，但与任一条链相邻的顶点总是另一条相反链中的顶点（如图10，a）。在A—B链的U形凹口内，必定是一支与其相反的C—D链。在A—B链的U形凹口两侧的某两个A或者两个B间，一定会存在着一个着有C或D的顶点（或者说在C—D链上，也一定存在着一个C点或D点，同时连接着A—B链上的两个A点或B点），改变这个顶点的颜色C或D为A或B，就可以使A—B链的U形部分闭合，形成环状，而使C—D链断开成为互不连通的两段（如图10，b）。当然了，同样也可以使图10中的C—D链的倒U形部分成为闭合的环形链，而使A—B链断开。这样，图4中的无环形链的构形就可以分别转化成图1的有环形链A—B的构形（如图8）或图2的有环形链C—D的构形（如图9）。

H—构形，按A—B链和C—D链的相互依存关系看，就只有以上图1到图7的七种情况，不会再有别的什么情况出现了。说明以上的7个图分别就是H—构形的7个不可避免的构形，由它们共同构成了H—构形的不可免集。这个不可免集是完备的。
2、5  H—构形可约性的解决办法：
看来，解决四色猜测的证明问题，主要就是要解决图1和图2的有环形链的构形中的待着色顶点V的可4—着色问题了。既然是因为有了双环交叉链，才构成了H—构形的，那就要想办法去断开它，使之从连通的链变成不连通的。使图转化成可约的K—构形就可以了。可以看出，只要改变了两链的共同起始顶点2A，两链的交叉顶点8A和两链各自的终了顶点4D和5C的颜色，就可达到断开双环交叉链的目的。

2、5、1  对于图1中的有环形链A—B的构形，交换A—B环内的经过4D和5C的C—D链（如图11），或者交换A—B环外的经过6C和7D的C—D链（如图12），都可以使双环交叉链断开，使图转化成可约的K—构形而可约。虽然所得到的图11和图12中仍含有两条连通链（如图中加粗的边所示），但却没有真正意义上的“十字”交叉，仍是可以连续的移去两个同色B的。所以该两图仍是可以空出四种颜色中任何一种的可约的K—构形。

2、5、2  对于图2中的有环形链C—D的构形，交换C—D环内的经过2A的A—B链（如图13），或者交换C—D环外的经过8A的A—B链（如图14），也都可以使双环交叉链断开，使图都转化成可约的K—构形而可约。由于所得到的图13和图14中都含有两条关于两个同色的、连通的、且是交叉的链（如图中加粗的边所示），但是不可能通过交换而空出两个同色，所以该图只能是可以空出除两个同色外的三种颜色之一的可约的K—构形。
  
2、5、3  对于图3中的既有A—B环形链又有C—D环形链的构形，用解决图1和图2中任何一种有环形链的方法来解决，都可达到断开双环交叉链的目的（如图15，图16，图17，图18）。虽然图17和图18中仍含有两条连通链，但却没有真正意义上的“十字”交叉，所以已不是H—构形而是K—构形了。
以上解决三种有环形链的构形所用的方法就叫“断链交换法”，因为它的交换能使双环交叉链断开。交换的过程是在环形链的内、外交换与其呈相反色链的任一条链即可。或都说是交换经过2A（或8A）的A—B链或者是交换经过4D（或5C）的C—D链。
2、5、4  对于图5到图7的三个图，前面已说了可与图1或图2进行同样看待。均可以视A—B链或C—D链中有一条是环形链，而对其是相反链的任何一条进行交换，都可使双环交叉链断开，使图转化成可约的K—构形而可约。
可以看出，实际上H—构形只是分成了有环形链的构形和无环形链的构形两大类不可免构形。前者用断链交换法进行解决，后者是在将其转化成前者后，再用断链交换法进行解决，或者可直接用断链交换法进行解决。
2、6  “九点形”构形：

当以上的各种H—构形中，当图的顶点数均减少到仍含有双环交叉链A—C和A—D的“九点形”构形时（如图19，图20，图21），除只有图2（或图9）的构形所对应的图20仍是H—构形外，而其他的构形所对应的图19和图21均成了可以连续的移去两个同色B的可约的K—构形。可见，含有双环交叉链只是构成H—构形的必要条件，而不是充分条件。少了双环交叉，就不能构成H—构形，但有了双环交叉，却不一定都是H—构形。
3、结论：
通过以上对四色猜测从理论和实践两个方面的证明，都证明了极大平面图的四色猜测是正确的，这也就证明了地图的四色猜测和任意平面图的四色猜测也都是正确的。至此，四色猜测就得到了证明是正确的。

雷  明
二○二○年三月十四日于长安

注：此修改稿已于二○二○年三月十七日在《中国博士网》上发表过，网址是：

天空之城

我给您建议，到淘宝花8元钱，买一个软件，WORD转化为PDF的，然后上传，没有图片，你自己都敷衍了事，叫别人怎么看？是不是不把这里的人当回事？你也太目中无人了吧？

雷明85639720

我的水平低，但是我告诉大家可以去《中国博士网》中去看。怎么能是“不把这里的人当回事？”又怎么能是“太目中无人了”呢？总比你把自已的论文称做“世界级”的论文要好一点吧！

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，