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

雷明85639720

（接上贴）

三十多年研究四色问题的总结

四色猜测的手工证明（修订稿）（四）
——证明四色猜测的十多种方法汇编
雷  明

二○一七年七月•西安

四、无割边的3—正则平面图是
可3—边着色的，四色猜测正确！
雷  明
（二○一七年四月二十二日）

1、泰特猜想是正确的
1880年泰特提出的猜想是：无割边的3—正则平面图的可3—边着色，等价于其可4—面着色。因为地图就是一个无割边的3—正则平面图，所以说如果泰特猜想正确，则只要进一步证明任何无割边的3—正则平面图都是可3—边着色的，就可使地图四色猜测得到证明是正确的。进而由地图的面着色就相当于其对偶图——极大平面图——的顶点着色，得知四色猜测对于极大平面图也是正确的。从而也就可以得到由极大平面图通过“减边”和“去顶”运算所得到的任意平面图的四色猜测也是正确的。四色猜测就可以得到证明是正确的。
1、1        从可3—边着色到可4—面着色
设一个3—正则平面图是可3—边着色的，即C边＝3。该图的每一个顶点都连接着三条边，这三条边一定是三种不同的颜色。
3—正则平面图的每一个面都是由这三种不同颜色的边所围成的，有可能是二色边的面，也有可能是三色边的面。这是一个组合方面的问题。
1、1、1  可3—边着色的无割边的3—正则的平面图的面着色数一定是4的证明：
把由各种颜色的边组合成的面着上不同的颜色时，就是对该图的面着色。该图面着色的最大色数C面是：由三个元素中取出两个元素的组合数C2＝C ＝3！／［2！×（3－2）！］＝6／2＝3，与取出三个元素的组合数C3＝C ＝3！／［3！×（3－3）！］＝6／6＝1的和，即C面＝C2＋C3＝3＋1＝4。当边所着的三种颜色分别是k1，k2和k3时，以上四种组合就是k1和k2，k1和k3，k2和k3，以及k1，k2和k3。缺少其中的任何一种组合（特别是缺少k1，k2和k3的组合）时，其面着色数都将是小于4（如3）的。所以也就有可3—边着色的无割边的3—正则平面图一定是可4—面着色的结论。
但这只是理论上的证明，只是证明了可3—边着色的无割边的3—正则平面图一定是可4—面着色的，并不是实际的染色操作。也并不是说k1、k2和k3的组合就一定是A色，而其他的k1和k2，k1和k3，k2和k3三种组合分别一定就是B、C、D三色。因为从可3—边着色的无割边的3—正则平面图看，除了2—边形面（如蒙古的地图）是由两条不同颜色的边构成的外，其他的面可以说很多都是由三种颜色的边所构成的，有些相邻的面也是如此。如正四面体的各个三边形面均是由k1，k2和k3三种颜色的边所构成的，但总不可能把相邻的面也都着上相同的颜色吧。所以说这只是理论上的证明，不是实际的染色操作。
由三种颜色的边所构成的三边形面，各面都两两相邻的，在进行面着色时，至少，也是最多也得用四种颜色，才能够把各个区域区分开来。整个图中的面最多也就占用四种颜色。
1、1、2  可3—边着色的无割边的3—正则的平面图的面着色主要有两种实际染色的操作方法：
1、1、2、1  第一种染色操作方法就是我们在上文《四色猜测是可以手工证明的》中所说的，就是证明平面图的不可免构形可性的着色方法。但在着色之前，要把可3—边着色的无割边的3—正则平面图，首先转化成其对偶图（即是每个面都是三角形面的极大的平面图），然后对这个对偶图去进行顶点着色。针对着色中出现的各种情况，再用平面图的各种不可免构形的单独着色方法去进行处理，最后一定能得到一个可4—着色的极大平面图，也就相当于得到了该无割边的3—正则平面图的可4—面着色。这种操作方法既能适用于对任意平面图的顶点着色，也能适用于对任意平面图的面着色，当然也包括对3—正则的平面图的面着色。

1、1、2、2  第二种染色操作方法是韦斯特和徐俊杰证明泰特猜想中用过的方法，我把它叫做颜色叠加法[3]。这一方法是根据可3—边着色的无割边的3—正则平面图的特点——图中有一条或若干条边2—色回路或边2—色圈，这些边2—色圈把图分成了若干个部分（每一部分中包括着不同数目的该3—正则平面图中的面）。把被边2—色圈所分成的各部分相间的染以两种不同的颜色（暂叫它为二色图）。然后再把被另两个不同的边2—色圈所分成的两个二色图上下叠加起来，就会得到用四种新的颜色着色的该无割边的3—正则平面图的面着色图，且相邻的面间没有相同的颜色（如图4—1）。
但这种颜色的叠加有一个缺点，四种颜色叠加后，只能产生四种新的颜色，不能满足四色猜测所说的颜色数一定小于等于4的要求。比如图1的图本来就是一个3—色图，最后却染成了4—色图。虽然颜色数没有超过四种，但却不是该图的面着色数，不符合实际。

我通过研究后，认为有些可哈密顿的无割边的3—正则平面图的面着色数是小于4的（如正六面体所对应的图）。这种图在用颜色叠加法染色时，若所用的两种边2—色圈中只要有一个边2—色圈是哈密顿圈时，颜色叠加的结果都得到一个4—面着色的图（如图4—2）；若所用的两种边2—圈都不是哈密顿圈时，颜色叠加的结果就可得到一个3—面着色的图（如图4—3）。
我们也给塔特所构造的非哈密顿的无割边的3—正则平面图和目前已知最小（顶点数最少）的非哈密顿的3—正则平面图，以及百多年来未能4—着色的赫渥特图的原型——一个3—正则的平面图（即地图），用以上两种方法都进行了面着色，证明了该三个图的面着色数都是等于4的（当然其也都一定是可以3—边着色的）。
根倨以上这样的情况，就要求在对无割边的3—正则的平面图进行面着色之前，首先要弄清所染色的图是不是可哈密顿的。然后再染色时，才能得到一个正确的染色结果。这一着色方法只能是对于无割边的3—正则的平面图的面着色时有用，而不能用于对任意平面图的面着色和顶点着色。

1、1、3  两个有关3—正则平面图的面着色色数的猜想：
根据以上给可3—边着色的无割边的3—正则的平面图采用颜色叠加法进行面着色的实践，我们发现：在颜色叠加时，所用的两种边2—色回路中至少有一个是哈密顿圈时，其面着色一定得用4种颜色：而两种边2—色回路都不是哈密顿圈时，其面着色的色数则一定是3。我们还发现：在面着色数是3时，两种边2—色回路都把图分成了三个以上的部分，图中所有的面也都是边2—色圈；而在面着色数是4时，至少有一种边2—色回路把图只分成了两部分，图中的面既有边2—色圈，也有3—色圈。又因为奇数据边面一定是3—色圈，所以最后又得出了，含有奇数边面的无割边的可3—边着色的3—正则平面图的面色数一定是4，而不含奇数边面的无割边的可3—边着色的3—正则平面图的面色数一定是3。
于是，我猜想：①所有面全都是边2—色圈的3—边着色的3—正则平面图的面色数一定是3；②所有面不全是边2—色圈的3—边着色的3—正则平面图的面色数一定是4。
1、1、4  3—正则平面图边、面着色的总色数：
整个无割边的可3—边着色的3—正则的平面图中最多用了多少种颜色呢，也是一个三个元素的各种组合的问题。一条边虽不能构成面，但它却也占用了一种颜色，边所占用的颜色数是C1＝C ＝3！／［1！×（3－1）！］＝6／2＝3，所以整个图中最多所用的颜色总数是：C总＝C1＋C2＋C3＝C ＋C ＋C ＝3！／［1！×（3－1）！］＋3！／［2！×（3－2）！］＋3！／［3！×（3－3）！］＝3＋3＋1＝7种。的确，3—正则平面图中的边色数与面色数的和最大就是7。
1、1、5  颜色叠加原理的理论分析：
地图的顶点都是三界点，都只连接着三条边（如图4—4），分别着以1，2，3三种颜色（如图4—4，a），每两条边之间所夹的区域用一种颜色当然是可以的，可以把1—2两种色边所夹的面用Ⅰ表示，把2—3两种色边所夹的面用 Ⅱ 表示，把1—3两种色边所夹的面用 Ⅲ 表示，只有三种颜色。但作为一个面，其边界一定是一个圈。若是偶圈，该面边界线只用两种颜色就可以了，该面可以着上Ⅰ，Ⅱ，Ⅲ 中的某一种颜色即可；但若是奇圈，该面边界线一定要用三种颜色来染色。这种情况，该面就不能用Ⅰ，Ⅱ，Ⅲ 中的任何一种，而只能用第四种颜色 Ⅳ（如图4—4，b）。这就是可3—边着色的无割边的3—正则平面图面着色时，可能会用到四种颜色的原因。

若把由两种颜色的边所夹的区域的颜色用两种颜色的交集表示，则由三种颜色的边所夹的区域的颜色就是三种颜色的交集。则有1∩2＝Ⅰ，2∩3＝Ⅱ，1∩3＝Ⅲ 和1∩2∩3＝Ⅳ。这也就是给任何可3—边着色的无割边的3—正则平面图（地图）的面染色时，至少要准备四种颜色的原因。
1、2  从可4—面着色到可3—边着色
设一个3—正则平面图是可4—面着色的，即C面＝4。所用的颜色分别是A、B、C、D四种。
图中的每一条边都是两种颜色的面的共同边界线，图中边界线的种类数就是由四个元素中取出两个元素的组合数，即C边界＝C ＝4！／［2！×（4－2）！］＝24／4＝6，即A—B、A—C、A—D、B—C、B—D、C—D六种。
1、2、1  互斥的边界线：
是不是六种边界线就得要用六种颜色呢，不是的。因为在3—正则的平面图中，由A色面和B色面所构成的边界线A—B，与由C色面和D色面所构成的边界线C—D，不但不可能是同一条边界线，而且也不可能相邻（如图4—5中加粗的边界线A—B和与带小园圈的边界线C—D）。象A—B和C—D这样的两条边界线就叫一对互斥的边界线。而互斥的边界线由于其互不相邻，所以着同一颜色是可以的。

互斥的两条边界线两侧的国家是完全不相同的，如中、蒙边界线的两侧是中国和蒙古，朝、俄边界线的两侧则是朝鲜和俄罗斯，中、蒙和朝、俄两条边界线就是互斥的边界线，两条边界线也是不相邻的；而两条边界线的两侧的国家有一个是相同的国家时，这样的两条边界线则是相邻的边界线，如中、蒙边界线与中、俄边界线就是相邻的边界线，因为这两条边界线的一侧有同一个国家——中国，这两条边界线的确也是相邻的；还有另外一种边界线，即两条边界线两侧的国家完全是相同的两个国家，这样的两条边界线虽不是同一条，但却是这两个国家在若干个不同地段处的边界线，如中国和俄罗斯就在两个地段处有两条边界线，中间夹有蒙古，把中、俄边界线隔成了两段；中国和印度在三个地段处有三条边界线，中间分别夹有尼泊尔和不丹，把中、印边界线隔成了三段。
1、2、2  互斥的边界线在3—正则的平面图中只有三对：
象A—B和C—D这样的一对互斥的边界线，在由A、B、C、D四种颜色的面所构成的边界线中，应该还有A—C和B—D，A—D和B—C两对，每对都可用同一种颜色。在可4—面着色的3—正则的平面图中，每个“三界点”顶点都与三种颜色的面（如A、B、C三种）相邻，该顶点所连的三条边界线分别是A—B，A—C和B—C；这三条边界线两两间，正好都是由该两条边界线所夹的国家的颜色构成的，都是相邻的边界线，所以这三条边界线是可以共同相交于一个“三界点”顶点的；这三条边界线中，正好也没有各条边界线所对应的互斥边界线C—D、B—D和A—D，这也就进一步说明了互斥的边界线也是互不相邻的；若把A—B，A—C和B—C三条边界线分别用1、2、3表示，则与其互斥的边界线C—D，B—D和A—D也可以分别用1，2，3来表示。在3—正则的平面图中，互斥的边界线一共只有三对。
1、2、3、可4—面着色的无割边的3—正则平面图一定是可3—
边着色的：
由四种颜色的面所构成的六种边界线中，有三对是互斥的边界线，互斥的边界线可用同一种颜色。由于这个3—正则的平面图是可4—面着色的，各面的颜色已经确定，那么各“三界点”顶点所连的边界线的颜色，实际上也是已经确定了的。全图中只有三对互斥的边界线，每对用一种颜色，那么，全图中的所有边界线实际上也就只有三种颜色。3—正则的平面图每个顶点都只连有三条边，正好每个顶点也就连有三种不同颜色的边。也由于每对互斥的边界线，分别是由两条在边界线两侧用了完全不同颜色着色的两个区域的边界线构成的，所以图中互斥边界线的总对数应该是C互斥对数＝C边界／2＝6／2＝3，这也就是该图边着色时的色数，即C边＝3。所以也就有可4—面着色的无割边的3—正则平面图一定是可3—边着色的结论。
1、2、4  用反证法证明可4—面着色的无割边的3—正则平面图一定是可3—边着色的：
假如这个图不是可3—边着色的，那么图中至少要有一条边是用了第四种颜色的。则这条边的两侧至少也要有一个面不是用A、B、C、D四种颜色之一着色的面。但这却是不可能的，因为该图是可4—面着色的，图中只用了四种颜色。假设与已知条件产生了矛盾，应该否定假设。这就使可4—面着色的无割边的3—正则平面图一定是可3—边着色的结论得到了证明。
由于该图的面色数是不大于4的，现在又证明了其边色数是3，所以图中所用的颜色总数仍是C总＝C面＋C边＝4＋3＝7，不大于7。与上面1中的结论是相同的。
1、3  泰特的猜想是正确的
现在已经证明了泰特的猜想是正确的。但还需要进一步证明每一个无割边的3—正则平面图都是可3—边着色的，才能使四色猜测得到证明是正确的。
2、无割边的3—正则平面图都是可3—边着色的
2、1  无割边的3—正则平面图一定可以3—边着色：
2、1、1  无割边的3—正则平面图一定可以划分为一个或若干个偶圈：
我们已经知道可3—边着色的无割边的3—正则平面图中的三种边2—色圈（回路）都一定是偶圈，所以首先要分析无割边的3—正则平面图中是否含有偶圈。
由于3—正则图的每个顶点都连着3条边，图中的总度数应是d＝3v（d是图的度数，v是图的顶点数），又因为一条边的两端就是两度，所以无割边的3—正则平面图的边数e＝3v／2＝1.5v，即边数是顶点数的1.5倍。为了保证图的边数是整数，无割边的3—正则平面图的顶点数还必须是偶数。从而也可以看出这种图的边数一定也是3的倍数。
因为无割边的3—正则的平面图中有e＝（∑epi）/2＝（ep1＋ep2＋……＋epn）/2的关系（式中ep是各面的边数），可以看出，无割边的3—正则平面图中若含有奇数边面时，则奇数边面的总个数也必须是偶数。如属于3—正则平面图的正四面体的所有面都是三边形面，奇数边面是偶数个；正十二面体的所有面都是五边形面，奇数边面也是偶数个；还有奇楞柱都只有两个面是奇数边面，还是偶数。
由于无割边的3—正则平面图的顶点数一定是偶数，并且图中的奇数边面的总个数也一定是偶数，这就保证了无割边的3—正则平面图一定可以划分成一个或若干个偶圈。图中若无奇数边面时，因图的顶点数是偶数，把图划分成一个或若干个偶圈是没有问题的；若图中含有奇数边面时，则其一定是偶数个，至少也要有两个。两个奇数边面相邻，本身就是一个偶圈；若不相邻时，则可以通过一个或若干个偶数边面的“传替”（即在这两个奇数边面中间一定夹有一个或若干个连续相邻的偶数边面）而构成一个较大的偶圈（如图4—6）。图4—6中两个三边形面与一个四边形面共同构成了一个有六条边的偶圈。

2、1、2  无割边的3—正则平面图一定可以3—边着色：
一个或若干个偶圈，总的顶点数还是偶数。这些圈中一定包括了图中所有的顶点，且圈中每一个顶点均与2条边相连接，偶圈中的边数与顶点数相同。偶圈以外的每条边的两端均连接着这些偶圈中的一个顶点，所以偶圈以外的边，实际上只有偶圈顶点数的一半，或者偶圈边数的一半，总的边数也是顶点数的1.5倍，图仍是一个无割边的3—正则的平面图。因为无割边的3—正则平面图的每一个顶点都连有3条边，且边数是顶点数的1.5倍。
因为偶圈边着色时两种颜色就够了，所以这些偶圈一定是一条或多条的边2—色圈。除此以外，图中的其他边（相当于顶点数的一半）都是两端均连结着该边2—色圈上的、且只连接着同样两种颜色的边的顶点；又因这些边之间互不相连，所以这些边是可以同时都着上与以上边2—色圈中两种颜色都不同的第三种颜色。图4—6中有两条2—3二色构成的边2—色圈（都是偶圈），两圈之外所有边都可着1色，全图的边共用了三种颜色。
这就证明了无割边的3—正则平面图一定都是可3—边着色的。
2、2  图的边着色
图的边着色，就是对其线图的顶点着色。所谓线图就是把原图的边作为顶点，按原图中边与边的相邻关系作新的边，所得到的新图，就是原图的线图（也叫边图）。
2、2、1  3—正则平面图中各顶点的度均是3，所以其线图中的最大团的顶点数最大也只能是3（即线图的密度是3），着色时至少也要用3种颜色。

2、2、2  3—正则平面图中各面的边数都是大于等于2的多边形面，这些多边形面在其线图中也都是以边数大于等于3的圈（面）出现的（如图4—7，a）。图4—7，a就是地图（3—正则的平面图）中的“两国夹国”这一情况。所夹国只有两条边界线（如蒙古只有中、蒙和俄、蒙两条边界线），是一个“2—边形”面，并且这个面的两条边界线是相邻的，构成了一个2—圈。这个2—边形面在边（线）图中则不是面，而是在两条边界线所对应的两个3—度顶点间的两条平行边，而平行边只相当于一条边；这条边又是该2—边形面边界上的两个“三界点”（图4—7，a中的小黑点顶点）所对应的两个三边形面（图4—7，a中的两个加粗边的三边形面）的一条公共边。所以3—正则平面图的线图的密度仍是3，所有的面也全都是边数大于等于3的圈（面）。圈在顶点着色时，色数也一定是不大于3的。所以该线图的色数一定是不会大于3的。
2、2、3  3—正则平面图中各边的两端都连着三条（如图4—7，a）或四条（如图4—7，b）边，表现在其线图中就是各顶点的度均是3或4。又由于3—正则平面图中各面的边数均大于等于2，所以其线图的各顶点的四周一定是三个或四个边数大于等于3的面。其线图中除了所有顶点都是处在一个4—轮的中心顶点的唯一一个正四面体的线图（如图4—7，b）外，再不可能有轮沿顶点数大于3的轮出现，更不可能有3—轮以上的奇轮出现。所以3—正则平面图的线图的色数也就不可能大于3。对于正四面体来说，一是由于正四面体的线图的顶点全是4—轮（偶轮）的中心顶点，而偶轮的色数都是3；二是因为正四面体边着色的实际色数，也正好是3。所以正四面体也是可以3—边着色的。
2、3  无割边的3—正则平面图的可3—边着色操作方法
以上以经证明了无割边的3—正则平面图都是可3—边着色的。但是给出一个具体的图，如何进行3—边着色，这又是一个具体的问题。
2、3、1  第一种操作方法是：按“1、1、2、1”中的第一种操作方法对其进行可4—面着色（首先也是把给出的无割边的3—正则平面图作对偶图，使其变成一个极大的平面图，再对这个极大平面图进行顶点着色），再按互斥边界线可着同一颜色的原则，把三对互斥边界线着以三种不同的颜色即可完成该图的可3—边着色。
2、3、2  第二种操作方法是：就是直接进行边着色。首先找一个三界顶点，把其所连的三条边分别着以1、2、3三种颜色，再分别从这三条边往下找另外的三界顶点，将与新找到的三界顶点所连的另外两条边，分别着以与已着过颜色的那条边的原有颜色（如1）不同的另两种颜色（2或3）即可。这样不停的找下去，就可给图中所有的与三界顶点所连接的边着上已经确定的1、2、3三种颜色之一，而决不会用到第四种颜色。但使用这种方法时一定要注意，不要把本来所有面都应是边2—色圈（如图4—3），着成了至少有一个面是3—色圈的图（如图4—2），即不要把偶数边面着成了3—圈就行了。

（未完，接下贴）

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，