直接用地图来证明四色猜测

雷明85639720

直接用地图来证明四色猜测
雷  明
（二○一七年三月二十日）

地图就是一个无割边的3—正则的平面图，其中的每一个顶点都连着三条边，这就是“三界点”，其附近区域就是平常所说的所谓的“三不管地区”。
1880年泰特曾猜想：任何无割边的3—正则平面图的可3—边着色与其可4—面着色是等价的。几乎所有的文献上都说泰特当年已经证明其猜想是正确的，但却没有看到泰特的原始证明。文献上只看到有邦迪、韦斯特与徐俊杰的证明，但都叫人看了后并不明白，也不好理解。如果说泰特的猜想是正确的，那么只要能证明任何无割边的3—正则平面图是可3—边着色的，也就证明了地图四色猜测是正确的。又因为给地图的面上的着色，就是对其对偶图——极大平面图——的顶点着色，从而也就说明了任何极大平面图的色数也是不大于4的；再进一步，因为对极大平面图通过“去点”和“减边”运算，所得到的任意平面图的色数只会减少，而不会增大，所以也就证明了任意平面图的色数也是不会大于4的。从而也就最终证明了四色猜测是正确的。本文作者也想试证一下。
1、可3—边着色的无割边的3—正则平面图一定是可4—面着色的
我们先给一个可以3—边着色的无割边的3—正则平面图的可4—面着色的实例，如图1的正6—面体。
1、1  这里采用的是颜色叠加法。其原理是：首先把1—2—1边2—色圈内、外的区域（该区域包括着该3—正则平面图的多个面）分别着以A（红）、B（兰）二色（如图1，a），再把1—3—1边2—色圈内、外的区域（该区域也包括着该图的多个面）分别着以C（黄）、D（绿）二色（如图1，b）。然后再把两张着过色的图片重叠起来，就会产生四种新的颜色AC（红）、AD（兰），BC（黄）和BD（绿）（如图1，c）。使图中的每一个面都只占用了一种颜色，而有共同边界的相邻两个面却没有共同的颜色。

1、2  可能有人会提问，四种颜色两两重叠（叠加）应该得到的是六种新的颜色，为什么却只产生了四种新的颜色，而不是六种呢，是乎好象还应该有AB 和CD。我们的回答是，按我们的操作方法，的确A和B、C和D是没有重叠的，所以就不可能产生AB和CD。按以上的操作，颜色叠加的结果最多只能产生AC，AD，BC和BD四种新的颜色。
1、3  可问题又来了，四色问题说的是任何地图染色时，色数都是小于等于4的，而这里只是得出了一个等于4，而不是小于等于4。另外，这个正6—面体本来就是一个3—色图，颜色叠加的结果却成了4—色的，是一个非正常的着色。对。这两个问题提得好。这个问题也一定是要解决的。
从图1中可以看出，该图中至少是有一条1—2—1边2—色圈是哈密顿圈；如果我们在对其进行边着色时，让图中任何一条边2—色圈都是不哈密顿圈时（如图2）。即任何相同的边2—色链，都至少是两个以上的偶圈，可以把画图的面分成三个以上的部分。这时，就可以做到使图的色数小于4，也可以使正6—面体的面着色数由4变为3，成为一个正常着色。

可见，用颜色叠加法，要保证任何无割边的3—正则平面图的面着色是一个正常着色，必须使其3—边着色的图中，各条边2—色圈都不
是哈密顿的。
但是，图果一个图除了只有可哈密顿的边2—色圈外，再无普通的边2—色圈时，仍是可以实现正常着色的。如图3的海地岛的地图。
1、4  有人可能还会说，海地岛的地图本来就只有3个面，根本就不可能着上4种颜色的。这也对。我们再看一个4—楞柱（或是有5个国家的海岛的地图），如图4。颜色叠加的结果与4—楞柱是3—面着色的相符，面色数是3。



    1、5  可能还有人会说，你举的几个例子本来就是3—面着色的3—正则平面图。如果本来就是4—面着色的3—正则平面图，通过颜色叠加是否也能得到一个4—面着色的图呢。回答是：这是一定的。因为它本来就不能用三种颜色着色，当然不可能得到一个3—色的图来。如图5的5—楞柱，它的面色数是4，用颜色叠加的结果，其面色数仍然是4。在5—楞柱的3—边着色图中，一定有一条边2—色圈是哈密顿的（如图5，b中的1—3—1边2—色圈），所以颜色叠加的结果，5—楞柱的面色数是4。
到此，就证明了可3—边着色的无割边的3—正则平面图都一定是可4—面着色的。
为了在使用颜色叠加法对无割边的3—正则平面图面着色时，作到正常的可4—面着色，首先要注意，在其3—边着色的模式中，一定不要含有哈密顿圈。
2、可4—面着色的无割边的3—正则平面图一定是可3—边着色的
设可4—面着色的3—正则图（地图）所用的四种颜色分别是A（红），B（兰），C（黄）和D（绿），着A（红）和B（兰）二色的两个图家的边界线，绝对不可能与着C（黄）和D（绿）二色的两个国家的边界线是同一条边界线，也不可能相连接。这样，两组完全不同颜色A、B和C、D所构成的两组相邻国家，其相应的红（A）兰（B）二色构成的边界线a—b和黄（C）绿（D）二色构成边界线c—d不但不可能是同一条，也是不可能是相连接的。这样的两种边界线染成同一颜色是完全可以的。四种颜色两两相邻的情况共六种：即A与B，A与C，A与D，B与C，B与D和C与D。这六种中，A与B和C与D是不可邻接的一对，A与C和B与D也是不可邻接的一对，A与D和B与C又是不可邻接的一对，共三对。

我们分别用1，2，3表示三种颜色的边：把由红（A）兰（B）二色构成的边界线a—b边和由黄（C）绿（D）二色构成的边界线c—d边都用1表示，把由红（A）黄（C）二色构成的边界线a—c边和由兰（B）绿（D）二色构成的边界线b—d边都用2表示，把由红（A）绿（D）二色构成的边界线a—d边和由兰（B）黄（C）二色构成的边界线b—c边都用3表示，得就可得到任何可4—面着色的3—正则平面图的3—边着色。如图6的3—楞柱和图7的正6—面体，他们的面色数分别是4和3，其边色数却都是3。

到此，就证明了任何可4—面着色的无割边的3—正则平面图（地图）都一定是可3—边着色的。
到此，也就证明了泰特的猜想：无割边的3—正则平面图的可3—边着色等价于其可4—面着色。泰特的猜想是正确的。
现在最重要的问题是：只要能证明任何无割边的3—正则平面图都是可3—边着色的，就可证明地图四色猜测和四色猜测是正确的。
3、任何3—正则平面图都是可3—边着色的
首先由于3—正则图的每一个顶点都连着3条边，那么该类图的总度数就是3v（v是图的顶点数），又因为一条边是两度，所以该类图的边数是e＝3v／2＝1.5v，即边数是顶点数的1.5倍。可以看出，只有当顶点数v是偶数时，才能保证这类图的边数是整数。所以又有这类图的顶点数一定是偶数的结论。
3、1  第一种证明方法；无割边的3—正则平面图都一定可以划分为一个或若干个偶圈
3、1、1  因为3—正则图的顶点数一定是偶数，这就为把图中的顶点划分成一个或若干个偶圈打下了基础。所以该图的顶点一定可以划分为若干个（包括一个）大于等于4的偶数个顶点的集团。在各集团内沿某条路线一定是可以得到一个包括集团内所有顶点在内的边2—色圈（即集图内的哈密顿时圈），这是毫无凝问的。这些圈的分布可以是大圈套小圈式的，也可以是并列式的，也可以是二者兼有的。剩下的圈内和圈与圈之间的边，都是该边2—色圈以外的边，其两端也都只连接着边2—色圈上的已着有1色或2色的顶点，并且他们又是互不相邻的，给他们全部着上第3种颜色是完全可以的。所以，无割边的3—正则平面图的边着色，是不会用到第四种颜色的。这就证明了无割边的3—正则平面图一定都是可以3—边着色的。如图8的无割边的3—正则平面图，就是一个可3—边着色的图（而图8，c则是一个有割边的3—正则平面图，它的边色数是4而不是3）。

3、1、2  我们从构造各种无割边的3—正则平面图的过程中可以看出，无割边的3—正则平面图（或地图）中不可缺少的面的边数是2，3，4和5，也就是说任何无割边的3—正则平面图（或地图）中一定都存在这四种面的一种或几种。这也就是坎泊所给出的地图的不可免集。海岛的地图中有只存在2—边形面的地图（如海地岛的地图）和3—边形面的地图（如一个海岛上只有三个国家的地图），正6—面体和正12—面体中分别只存在4—边形面和5—边形面，而他们都是唯一只有一个哈密顿圈（偶圈）的3—正则平面图或地图。除此以外，其他的无割边的3—正则平面图（或地图）中至少都存在着3—边形面，4—边形面，5—边形面中的两种或三种。如果图中存在着4—边形面，首先就可以划分出一个4—边形的偶圈来，然后再从这个4—边形的偶圈外面划分出其他的偶圈来即可。这是一定可以办到的。
3、1、3  现在就只剩下只有3—边形面和5—边形面共存的一种情况了。在这一情况中，两个3—圈有边相邻时，拼接起来就得到一个偶圈，两个5—圈有边相邻时，拼接起来也就得到一个偶圈，一个3—圈与一个5—圈有边相邻时，拼接起来也就是一个偶圈。但却不可能有有只有一个顶点相邻的圈，因为这样的相邻顶点的度就变成了4，图就不再是3—正则的了。如果这些圈不直接有边相邻时，不能直接拼接，那么还可以通过其他的偶圈或奇圈进行“传替”，以达到其简接拼接的目的，从而可划分出一个偶圈。然后再在其外划分出别的偶圈即可。
3、1、3  至此，就证明了任何无割边的3—正则平面图一定是可以划分为一个或若干个偶圈的。也就保证了无割边的3—正则平面图一定是可以3—边着色的。
3、2  第二种证明方法：无割边的3—正则平面图的线图都是可3—（顶点）着色的

3、2、1  因为图的边着色就是对其对边图（即线图，线图即把原图的边作为新的顶点，并按原图中边与边的相邻关系作新边所得到的图）的顶点着色，而3—正则图的边图又是一个密度（即图中最大团的顶点数）是3的平面图（如图9中加粗的边和加大的顶点所构成的图），并且是一个4—正则的平面图（因为原3—正则图中每一条边的两个端总共均连着4条边，所以就有其边图中每个顶点均连有四个顶点）。但这个4—正则平面图只是从对无割边的3—正则平面图作线图而得到的4—正则平面图，并不是指任意的4—正则图平面图。
3、2、2  由于无割边的3—正则平面图的边图的最大团是一个K3团，其顶点数就是该图的密度，所以该图着色时最少也要用三种颜色；又由于该图中最大的轮是4—轮，所以其色数最大也只能是3；也由于无割边的3—正则平面图中有边数大于3的面，所以其边图中也一定会存在边数大于3的多边形面，即边数大于3的圈（如图11），而圈的着数最多也只要三种颜色就够了。基于这三点，就能够决定该图的色数是3而不会是4。

3、2、3  通过画图，还可以看出，除了正4—面体（即K4图）这个3—正则平面图中每个面都是三角形面，其线图中的每一个顶点都处在一个4—轮的中心顶点（如图10，该图的色数是3）外，其他的3—正则平面图中，至少都会含有一个面的边数是大于等于4的。这样的3—正则图的线图中，至少会有一个面的边数大于等于4的多边形（如图11）。处在这种多边形顶点上的、属于图中的顶点，其度仍一定是4（因为该边图本来就是一个4—正则的平面图），是不可能位于一个大于4的轮的中心顶点位置的，这个边数大于等于4的多边形面，也是不可能与别的顶点构成轮沿顶点数是大于等于4的轮的，特别是不可能构成轮沿顶点数是大于等于3的奇轮。这也就决定了该边图的色数只能是3而不会是4。
3、3  泰特猜想是正确的
通过以上的1、2两节，已经证明了泰特的猜想是正确的。当然了，要说泰特的猜想是错的也未尝不可，毕竟他所依据的前提是一个错误的“每个平面三次图都有哈密顿圈”的猜想（许寿椿教授在他的《图说四色问题》一书中就把“每一个三连通平面三次图D都有哈密顿圈”定义为泰特猜想的）。但是，我们在上面的证明中却是用了任意的无割边的3—正则平面图，其中有可哈密顿的，也有不可哈密顿的。看来，图是不是哈密顿的并不重要，而重要的是这些无割边的3—正则平面图都是可3—边着色的。因此可以说，任何无割边的3—正则平面图（地图）是不是都可4—面着色，关键的问题是要证明任何无割边的3—正则平面图都是可3—边着色的。
4        四色猜测的证明
由于已证明了“无割边的3—正则平面图的3—边着色等价于其4—面着色”的泰特猜想是正确的，现在我们又证明了任何3—正则平面图都是可以3—边着色的，这就证明了任何地图（即无割边的3—正则平面图）都是可4—面着色的。地图四色猜测是正确的。
给地图中面上的染色，实际上就是给地图的对偶图——极大平面图——的顶点着色，所以说任何极大平面图也都是可4—着色的。又因为极大平面图经“去点”和“拆边”运算后，所得到的任意平面图的色数只会比极大图减少而不会增大，所以又可以说任何平面图也都是可4—着色的。平面图的四色猜测也是正确的。
到此，就最终证明了四色猜测是正确的。四色猜测是可以手工证明的，不用计算机也是可以的。

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

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

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，