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

雷明85639720

（接上贴）

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

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

二○一七年七月•西安

3、 对无割边的3—正则平面图都是可3—边着色的检验
设有n个面的无割边的3—正则平面图是可3—边着色的，现在证明有n＋1个面时，其也是可3—边着色的。
在一个面数为n的无割边的3—正则平面图的某个面内增加一条边，把一个面分为两个面，就成了有n＋1个面的无割边的3—正则平面图。在某个面内的任两条边中各取一个点a和b，并把a和b用边相连接，a和b就变成了两个新的“三界点”，边a—b就把一个面分成了两个面，图中也就增加了一个面，成为n＋1个面。同时图中也增加了两个顶点和三条边，增加的边数也是增加的顶点数的1.5倍，符合3—正则平面图的要求。
现在只要证明这个图还是一个无割边的3—正则平面图和仍是可3—边着色的就可以了。
3、1  证明这个有n＋1个面的图仍是一个3—正则的平面图
因为无割边的3—正则的平面图中有e＝（∑epi）/2＝（ep1＋ep2＋……＋epn）/2的关系（式中ep是各面的边数），所以3—正则平面图中奇数边面的总个数一定是偶数。
3、1、1  a和b两点所在边的两个相邻面的边数的改变对3—正则平面图中的奇数边面的总个数的影响：
3、1、1、1  若a和b两点所在边的两个相邻面原来都是偶数边面时，现在则都成了奇数边面，奇数边面增加了两个，但偶数（原有）＋2（增加）仍是偶数，奇数边面的总个数仍是偶数；
3、1、1、2  若a和b两点所在边的两个相邻面原来都是奇数边面时，现在则都成了偶数边面，奇数边面减少了两个，但偶数（原有）－2（减少）仍是偶数，奇数边面的总个数仍是偶数；
3、1、1、3  若a和b两点所在边的两个相邻面原来的边数是一奇一偶时，则现在奇数条边的面变成了偶数条边，而偶数条边的面则变成了奇数条边，但仍是一奇一偶，奇数边面的总个数没有发生变化，仍是偶数。
可见，a和b两点所在边的两个相邻面的边数的改变对3—正则平面图中的奇数边面的总个数一定是偶数并无影响。
3、1、2  被a和b两点分成两个面的那个面边数的变化对3—正则平面图中的奇数边面的总个数的影响：
3、1、2、1  若被分开成两个面的那个面原来是奇数条边时，该面现在的边数则是比原来多了两条的奇数，所分成的面只能是一个奇数边面和一个偶数边面。这等于说图中减少了一个原来的奇数边面，除了增加了一个偶数边面外，又增加了一个奇数边面，相当于图中奇数边面的总个数并未发生变化，仍是偶数；
3、1、2、2  若这个被分开成两个面的面原来是偶数条边时，该面现在的边数则是比原来多了两条的偶数：
①　一种情况是分成两个偶数边面，图中奇数边面的总个数根本就没有发生变化，还是偶数；
②　另一种情况是分成两个奇数边面，等于说图中减少了一个原来的偶数边面，但又增加了两个奇数边面，但偶数（原有）＋2（增加）仍是偶数，奇数边面的总个数仍然是偶数。
可见，被分开成两个面的那个面边数的变化对3—正则平面图中的奇数边面的总个数一定是偶数也没有影响。
3、1、3  有n＋1个面的图仍是一个无割边的3—正则平面图：
以上是从被a、b所分面与a、b两顶点所在边的相邻面两种面的边数变化来分析的，结果都是图中的奇数边面的总个数仍是偶数。原来有n个面的奇数边面的总个数是偶数，现在有n＋1个面的奇数边面的总个数仍然是偶数，符合无割边的3—正则平面图的要求。该图仍然是一个无割边的3—正则平面图，说明了有n＋1个面的图仍是一个无割边的3—正则平面图。
3、2  证明这个有n＋1个面的图仍是可3—边着色的
现在再来看看a和b两点所在边原来所着的颜色对这个有n＋1个面的无割边的3—正则图的3—边着色有什么影响。
图中因为增加了一个面而增加的两个顶点a和b，a—b边虽不能单独构成一个偶圈，但它却是在原图中两条边上新增加的顶点（如图4—8～图4—14）。这两个顶点可能处在同一个边2—色圈上，也可能处在不同的边2—色圈上。
3、2、1  a、b两顶点处在同一个边2—色圈上的情况：
a、b两顶点处在同一个边2—色圈上的情况（如图4—8、图4—9和图4—10）：


这种情况不管a、b两顶点所处的边原来着色是相同还是不同，也不管被a—b边所分的面是奇数边面还是偶数边面,更不管a、b两顶点所处的边原来是相邻还是不相邻（如图4—8，a、图4—9，a和图4—10，a），都可以对a—b边同一侧（比如左侧）的边2—色圈中所有边的颜色进行交换（如图4—8，b、图4—9，b和图4—10，b。这种交换并不会影响到着第三种颜色的边），使该边2—色圈中所增加的两条边分别着上该边2—色圈中的两种颜色之一，该圈仍是同原来颜色相同的一个边2—色圈；而把边a—b着上第三种颜色即可（如图4—8，b、图4—9，b和图4—10，b）。图仍是一个可3—边着色的3—正则平面图。

图4—8是a、b两顶点所在边不相邻且着色相同，所分的面是奇数边面的情况，图4—9是a、b两顶点所在边不相邻且着色不相同，所分的面是偶数边面的情况，图4—10是a、b两顶点所在边相邻且着色不相同（两边相邻时不可能着相同的颜色），所分的面是奇数边面的情况；而a、b两顶点所在边不相邻且着色相同，所分的面是偶数边面的情况和a、b两顶点所在边不相邻且着色不相同，所分的面是奇数边面的情况，以及a、b两顶点所在边相邻且着色不相同，所分的面是偶数边面的情况，同样都可以这样处理。
3、2、2  a、b两顶点处在不同的边2—色圈上的情况：
a、b两顶点处在不同的边2—色圈上的情况（如图4—11、图4—12、图4—13和图4—14）：

在这种情况下，a、b两顶点只能分别处在两个相同颜色的边2—色圈上（如图4—11，a），而不可能处在不同颜色的边2—色圈上。因为如果两个边—2色圈上有一种颜色不相同，则这两个边2—色圈至少就需要占用三种颜色，而与这两个边2—色圈相联系的边，则就必须用第四种颜色（如图4—11，b和图4—11，c）。这便与已知的有n个面的3—正则平面图是可3—边着色的条件产生了矛盾。所以a、b两顶点是不可能处在不同颜色的边2—色圈上的。这种a、b两顶点处在具有相同颜色的不同的边2—色圈的情况，也不可能有a、b两顶点所处的边是相邻的情况，因为a、b两顶点根本就不在同一个边2—色圈上。
3、2、2、1  图4—11，a的情况是属于a、b两顶点所处的边原来着色是相同的情况。这种情况实际上a、b两顶点又是处于同一个边—2色圈（如图4—11，a中是2—3二色的边2—色圈）上的，实际上也是属于上面3、2、1中“a、b两顶点处在同一个边2—色圈上的情况”，已经得到了解决。
3、2、2、2　当a、b两顶点真正处在不同的两条相同颜色构成的边—2色圈上的情况下，如果a、b两顶点所处的边原来着色是相同的（如图4—12，a），则a、b两顶点实际上也是处于相同的另一条边—2色圈上的（如图4—12，b中的1—3二色的边—2色圈），也属于上面图4—8一类的情况，是可3—边着色的（如图4—12，c，图中的a—b边着色2）。


3、2、2、3　当a、b两顶点真正处在不同的两条相同颜色构成的边—2色圈上的情况下，如果a、b两顶点所处的边原来着色是不同的（如图4—13，a和图4—14，a），也不管被a—b边所分的面是奇数边面还是偶数边面，都可对其中一个边2—色圈中各边的颜色进行交换（也比如左侧的边2—色圈。当然这种交换也是不会影响到着第三种颜色的边的），便可以使a、b两顶点又处在同一个另外两种颜色的边2—色圈上（如图4—13，b和图4—14，b都是2—3二色的边2—色圈），使问题变成如上面的第一种情况——“a、b两顶点处在同一个边2—色圈上的情况”，用与其相同的办法可以使图进行3—边着色（如图4—13，c和图4—14，c中的a—b边着色1）。图仍是一个可3—边着色的3—正则平面图。

到此，就证明了任何一个无割边的3—正则平面图都是可3—边着色的。
以上我们是对有n＋1个面的无割边的3—正则平面图进行证明的，同样的也可以对有n－1个面的无割边的3—正则平面图证明是可3—边着色的。这只要从有n个面的3—正则平面图中去掉一条边即可办到。
现在已经证明了无割边的3—正则平面图都是可3—边着色的，这也就等于验证了任何无割边的3—正则平面图也都是可3—边着色的结论是正确的，也就验证了任何无割边的3—正则平面图都是可4—面着色的结论也是正确的。最终也就验证了地图四色猜测是正确的。
4、四色猜测的证明
我们已经证明了泰特的猜想：“无割边的3—正则平面图的可3—边着色，等价于其可4—面着色”是正确的。现在又证明了每一个无割边的3—正则平面图都是可3—边着色的。当然也就证明了任何无割边的3—正则平面图（地图）也都是可4—面着色的，即证明了地图四色猜测是正确的。地图四色猜测是正确的，则其对偶图——极大图平面图——的顶点着色的色数也一定是小于等于4的，进而由极大平面图经“减边”和“去点”得到的任意平面图的色数也一定是不会大于4的，平面图的四色猜测也是正确的。到此也就证明了四色猜测是正确的。

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

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

五、用增加图的色数证明四色猜测的两种方法
雷  明
（二○一七年三月十一日）

1  根据不可同化道路原理，证明四色猜测是正确的
1、1  作一个图的色数比原图的色数大1的方法之一——不可同化道路法：
这里的“同化”即图论中的“收缩”，且只是指不相邻顶点间的收缩。“不可同化道路”是指图中某最大团外的一条道路，该道路总有一个顶点同化不到最大团中去。

若在一个最大团Kn外有一条道路，这条道路的所有顶点都与最大团中的同一个Kn－2团的各顶点均相邻，同时道路的两个端点顶点又都与最大团中另一个K2团中的一个顶点相邻。这样，道路中除了两个端点顶点只能向那个K2团的某一个顶点同化外，道路中的其他顶点均是可向这个K2团中的任一个顶点同化（如图5—1）。
当道路的两个端点顶点分别与K2团中的一个顶点相邻时（如图5—1，a），同时道路又是奇数顶点时，道路中总是有一个顶点同化不到最大团中去：而当道路的两个端点顶点都与K2团中的同一个顶点相邻时（如图5—1，b），同时道路又是偶数顶点时，道路中也总是有一个顶点是同化不到最大团中去的。
1、2  色数为n的图一定可以同化为一个Kn图：
根据已经证明是正确的哈德维格尔猜想，一个色数为n的图，一定是可以同化为一个Kn图的。因为图中不相邻的顶点才可以使用同一颜色，而不相邻的顶点也是可以同化为一个顶点的，所以哈德维格尔猜想是正确的。由色数为n的图同化成的Kn图，就是该图的最小完全同态，其顶点数n就是图的色数。图的最小完全同态是一个完全图，而完全图的色数也就是其顶点数。
现在我们对图的完全同态Kn用不可同化道路原理使其色数增大，只要不可同化道路系统不是非平面图，图的色数又不大于4时，就说明四色猜测是正确的；否则，若系统仍是平面图，而只要有一个图的色数是大于4时，四色猜测就是错误的。
1、3  对各种团作不可同化道路：
K1团，色数是1，它本身就是一个平面图，图中就只有一个顶点，没有任何边，不可能存在不可同化道路。也没有任何一个图是可以同化成K1图的；
K2团，色数是2，作不可同化道路并同化后是一个K3团，仍是平面图（如图5—2）。色数是3，虽比原来增大了1，但却小于4；
K3团，色数是3，作不可同化道路并同化后是一个K4团，也是平面图（如图5—3）。色数是4，虽也比原来增大了1，但却也不大于4；
可见顶点数小于4的团，作不可同化道路并同化后的图仍然是平面图，其色数都不大于4。


K4团作不可同化道路时，图中就出现了交叉边，变成了非平面图，同化后则是一个K5团（如图5—4），不再是四色猜测所研究的对象了。所以说平面图中的K4团是没有不可同化道路的。
    因为K5团本身就不是平面图，本身就不是四色问题研究的对象，所以这里也就不对其再作不可同化道路了。
1、4  K4团作了不可同化道路后不再是平面图的证明：
K4团的顶点数是4，边数是6；不可同化道路Pn的顶点数是n，边数是n－1；K4团与Pn道路相邻的边数是2n＋2；整个系统的顶点数是4＋n，边数是6＋n－1＋2n＋2＝3n＋7；顶点数是4＋n的平面图最大边数只可能是3×（4＋n）－6＝3n＋6；显然3n＋7＞3n＋6，所以对K4团作了不可同化道路后，就不再是平面图了。

1、5  四色猜测是正确的
从以上对平面图的各种团所作不可同化道路后所得的图看，在没有出现交叉边之前，即图没有变成非平面图之前，所有图的色数都是小于等于4的。这就证明了任何平面图的色数都是不大于4的。四色猜测得到证明是正确的。
2  根据米歇尔斯基操作原理，用反证法证明四色猜测
2、1  作一个图的色数比原图的色数大1的方法之二——米歇尔斯基操作法：
数学家狄拉克1953年在其论文《k—色图的构造》一文中提出一个问题：对于任意大的一个正整数k，是否存在一个图，不包含三角形但色数是k？这一问题分别在1954年和1955年分别由勃兰克•斯德卡兹和米歇尔斯基独立的作出了回答。米歇尔斯基（Mycielski）给出的由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法是：设Gk的顶点是v1，v2，……，vn,，添加点u1，u2,……，un和点u0。将ui与vi所有相邻顶点及u0相连，1≤i≤n。如此得到的图就是一个不含三角形的k＋1色图。
这里所说的不含三角形的图实际上就是基图Gk的密度是小于3的图。米歇尔斯基的这一构造方法在图论界把它叫做Mycielski—操作，简称M—操作。M—操作过程又是可以递推的，即可以多次进行的。每进行一次M—操作，图的密度（或最大团）并不发生变化，但其色数却增加1。于是，就有了“存在无三角形且色数任意大的图”[4]的说法。实际上，进行M—操作时的基图的密度可以是任意的，不一定都得是密度小于3的图。所以也就有“在各种密度下都有色数是无穷大的图”。请注意，这时所说的是图，而不是平面图。
米歇尔斯基操作法：是在有v个顶点的、色数是k的图外，作一个有u个星点顶点的u—星（注意，星的总顶点数是u＋1），并使u＝v。然后再把u—星中的星点顶点ui（1≤i≤u＝v）与原图中与ui相对应的顶点vi的所有相邻顶点都用边连接起来（注意，u—星的中心顶点u0是与原图中的任何顶点都不相邻的），这时所得到的图的色数就比原图的色数大1，且图中的最大团不变。
M—操作后，只所以最大团保持不变，是因为每个星点顶点都只和原图中与其对应的顶点的相邻顶点相邻，而与这个对应顶点并不相邻，所得到的团的顶点数仍与原图中最大团的顶点数是相等的。只所以所得图的色数一定比原图的色数大1，是因为u—星中的u个星点顶点均是不相邻的，他们可以同化（凝结）成一个顶点。这时，u个星点顶点所凝结成的这个顶点，又与原图中的所有顶点都相邻了，这个顶点只能着原图中所用颜色以外的另一种颜色（因为u—星的中心顶点与原图中的任何顶点都不相邻，所以给其着上原图中的任何一种颜色都是可以的）；另一个原因是，因为u—星的各星点顶点和原图中与其相对应的顶点均不相邻，可把这u个星点顶点着以和原图中与其相对应的顶点相同的颜色，这样u—星的星点顶点就占用完了原图中的所有颜色，剩下的u—星的中心顶点u0因与各星点顶点均相邻，所以就只能着以原图中所用颜色以外的另一种颜色了。
2、2  平面图的M—操作：
现在我们对任意的平面图进行M—操作：假设四色猜测是正确的，那么就有任何平面图的色数都是小于等于4的结论。若M—操作后，得到的图不再是平面图了，不管其色数是多少，就都不再是四色问题研究的对象了，因为色数小于等于4的图不一定都是平面图。如K3，3图，色数虽是2，小于4，但却是一个非平面图；若M—操作后，得到的图仍是平面图，但其中只要有一个图的色数大于4，则就可以否定假设，得出四色猜测不正确的结论；若M—操作后，得不到色数大于4的平面图，就应该肯定假设是对的，四色猜测是正确的。
2、2、1  图中无圈的情况（即只有一个面的情况）：
当图是K1时，色数是1，M—操作的结果，色数比原图大1是2，但不大于4，仍是平面图（但不连通），如图5—5；
当图是K2时，色数是2，M—操作的结果，色数比原图大1是3，也不大于4，也仍然是平面图（5—圈），如图5—6；


当图道路时，色数也是2，M—操作的结果，色数比原图大1是3，也不大于4，仍是平面图，但图中既有了4—圈，也有了5—圈，如图5—7；
当图是树（包括3—星这样最简单的树）时，色数也是2，M—操作的结果，色数比原图大1是3，虽不大于4，但却成了一个非平面图，如图5—8。已不再是四色猜测研究的对象了；
2、2、2  图中有圈的情况（即有两个以上面的情况）：
当图是一个3—圈（即K3图）时，色数是3，M—操作的结果，色数比原图大1是4，但不大于4，仍是一个平面图，图中不但有3—圈，也有了4—圈，如图5—9；
当图是一个4—圈时，色数是2，M—操作的结果，色数比原图大1是3，虽不大于4，但却成了一个非平面图，如图5—10；也已不再是四色猜测研究的对象了；

当图是一个5—圈时，色数是3，M—操作的结果，色数比原图大1是4，虽不大于4，但却也成了一个非平面图，如图5—11；也已不再是四色猜测研究的对象了；
可见，边数大于等于4的圈，进行了M—操作后的图，都会成为非平面图了，就不再是四色猜测研究的对象了。
2、3  除了3—圈（即K3团）以外的面数大于2的图进行M—操作后都不再是平成图的证明：
M—操作时，要先画一个星，该星只能画在一个面内。若图中有边数大于等于4的面（即4—圈）时，对这个4—圈进行M—操作后得到的是一个非平面图，所以含有边数大于等于4的圈的图，进行M—操作后的图就不再是平面图了；
若图是一个三角剖分图，所有面全是3—圈，M—操作中n—星的中心顶点u0一定要位于某个面以内，有关星点顶点若与位于该面边界上的顶点用边相邻时，是不会产生相交叉的边；但当n—星的有关星点顶点与位于该面边界以外的顶点用边相邻时，必然要产生相交叉的边，图也就变成了一个非平面图；
因此，图中面数是2的图，除了3—圈（即K3图）外，进行M—操作后的图均是非平面图；
含有轮的图中，其面数都是大于2的图，所以含有2—轮（有平行边的K3团或3—圈）和3—轮（即K4团）的图M—操作后的图也一定是非平面图。
2、4  除K1图外任可平面图都不可再进行第二次M—操作：
以上M—操作后的图仍是平面图的只有K1，K2，道路PN和K3（即3—圈），现在再看这些图是否还可以进行第二次M—操作：
K1图M—操作一次后，是一个K2图，是平面图（如图5—5），色数是2；这个图再进行一次M—操作后，一定是如图5—6那样的图，是一个5—圈，也是平面图，色数是3，仍不大于4；但因5—圈进行M—操作后是一个非平面图，所以K1图也只能进行两次M—操作；
K2图M—操作一次后，是一个5—圈（如图5—6），5—圈再进行M—操作后的图是一个非平面图，所以K2图也只能进行一次M—操作；
道路Pn进行M—操作一次后，所得图中既有4—圈，又有5—圈（如图5—7），因为这两种圈进行M—操作后的图都是非平面图，所以道路也只能进行一次M—操作；
3—圈（即K3图）M—操作一次后，图中既有3—圈，又有4—圈（如图5—9），因4—圈再进行M—操作后的图是非平面图，所以3—圈（即K3图）也只能进行一次M—操作。
除了以上这些图以外，其他任何平面图的面数都是大于等于2的。而除了3—圈外的任何面数大于等于2的平面图，在进行一次M—操作后的图都是非平面图，也就都不再是四色问题所研究的对象了。
2、5  四色猜测是正确的
以上我们对任意的平面图都进行了M—操作，M—操作后的结果仍是平面图的图的色数都是不大于4的，这就证明了开始的假设是正确的。任何平面图的色数都是不会大于4的，四色猜测是正确的。

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

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

（未完，接下贴）

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，