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

雷明85639720

（接上贴）

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

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

二○一七年七月•西安

二、我研究四色问题的思想方法
雷  明
（二○一七年元月十日）

1、把一个无限问的题变成有限的问题
图有平面图，有非平面图；平面图中又有道路，树，圈，轮，完全图，极大图等多种种类；每一种类中又有无限多的图，每个图的顶点又可以是无限多的，每个顶点的度也可以是无穷多的；四色问题就是与这些取值是无限多的参数交织在一起，也成了一个无限的问题。
1、1  平面图的着色
不管平面图是如何的复杂，着色时总是一个一个顶点去着的，当遇到待着色的顶点的相邻顶点已占用完了四种颜色时，总可以把该顶点周围的色圈想办法断开，使这个色圈中减少一种颜色。这就是“破圈”。
1、2  破圈着色法
可以把待着色顶点外面的色圈中使用次数最少的颜色的顶点，作为切入点，把该顶点的颜色去掉，并把该种颜色给这个待着色的顶点着上。与此同时，又将产生一个或多个待着色的顶点。新的待着色顶点周围若仍占用完了四种颜色时，就再继续的“破圈”，否则，新的待着色顶点就可着上图中已用过的四种颜色之一。
1、3  待着色顶点的着色
当图中除了待着色顶点外，所有的顶点都已着上了四种颜色的一种，也不存在相邻两顶点着有同一颜色时，有以下几种情况：
1、3、1  当待着色顶点的相邻顶点所占用的颜色少于四种或者该顶点的度小于等于3时，直接就可以给该顶点着上第四种颜色。
1、3、2  当待着色顶点的相邻顶点已占用完了四种颜色，且其度大于等于6时，就用破圈法；一直破下去，一定能找到一个新待着色顶点的度是小于等于5的；因为任何平面图中一定存在着至少一个顶点度是小于等于5的顶点。
1、3、3  以顶点度小于等于5的顶点构成的轮形构形，就是平面图的不可避免构形，轮的中心顶点叫做待着色顶点，用V表示，轮沿顶点叫做围栏顶点，简称“围栏”。这些不可避免的构形只要是可约的，即待着色顶点是可以着上四种颜色之一时，平面图的四色猜测就是正确的。由这些不可避免的构形构成的集合，就是平面图的不可免集。
1、3、4  若最后一个待着色顶点的度是小于等于4的，它一定是可以着上四种颜色之一的，因为坎泊已经用他创造的颜色交换技术的三种作用之一——“空出颜色”的交换，证明了这种构形是可约的。
1、3、5  所谓颜色交换技术，就是把由两种颜色交替进行着色的道路（这种道路在着色中叫做色链，简称“链”）中各顶点所着的颜色互换，就叫做颜色交换，简称“交换”。把可空出颜色给待着色顶点的交换，即通过交换可以从围栏顶点中空出一种颜色来，给待着色顶点着上的交换就叫“空出颜色”的交换。这种交换一定是从围栏顶点开始的，交换的链是由两个对角围栏顶点的颜色构成的色链，但该链在两个对角围栏顶点间必须是不连通的，也就是说所交换的链中，只可能含有一个顶点是5—轮围栏上的顶点，否则是不能空出颜色的。
1、3、6  但是，在有些平面图中却不一定都存在度小于等于4的顶点，如正二十面体所对应的图，各顶点的度都是5，没有顶点度小于等于4的顶点，所以证明5—轮构形是否可约也就成了一个关键。
1、4  5—轮构形
把5—轮构形的轮沿顶点的名称用1，2，3，4，5表示，相应的各顶点所着的颜色用B，A，B，D，C表示。这样的5—轮构形可表示成123—BAB型5—轮构形（如图2—1）。

1、4、1  1879年，坎泊只证明了5—轮构形中的：①无连通链，②只有一条连通链，③有B—C和B—D两条交叉的连通链和④有A—C和A—D两条连通链有共同的起始顶点2A、且链的中途没有交叉顶点的这四种情况下，5—轮构形都是可约的；而没有证明A—C和A—D两条连通链既有共同的起始顶点2A，但两链在中途又有相交叉顶点时的这一情况是否可约。这是坎泊证明中的一个疏漏。
1、4、2  在A—C和A—D两链既有共同的起始顶点2A，中途又有相交叉顶点（如图2—2中的顶点8）的情况中，也有可以同时移去两个同色B，空出B给待着色顶点着上的构形。如“九点形”构形中的含有A—B环形链（如图2—2，a），和既不含有A—B环形链，也不含有C—D环形链的情况（如图2—2，b和图2—2，c），都可以同时移去两个同色B。其他的一种情况（如图2—2，d，图中含有环形的C—D链）则是不能同时移去两个同色B的构形。这就是坎泊证明中漏掉了的那种构形。

1、4、3  1890年，赫渥特构造了一个图，图中的A—C和A—D两链既有共同的起始顶点2A，中途又在顶8A处相交叉的情况的图，该图也是不能同时移去两个同色B的。赫渥特就是用这个图指出了坎泊的证明中有漏洞的。可惜赫渥特和坎泊都并没有把这个漏洞补上。
不能同时移去两个同色B是赫渥特图型构形的特点，把这种构形叫赫渥特构形，用H—构形来表示；而把坎泊已证明是可约的构形和所有可以同时移去两个同色B的构形统一叫做坎泊构形，用K—构形来表示。所以就目前看，证明H—构形是否可约就成了证明四色猜测的一个最关键的问题了。
到此，我们就把一个无限的四色问题变成了一个有限的问题。
2、5—轮构形都是可约的
2、1  H—构形
2、1、1  H—构形又有四种情况：①只含有一条A—B环形链的（图2—3，a）；②只含有一条C—D环形链的（图2—3，b）；③既含有A—B环形链，又含有C—D环形链的（图见下一篇文章中的敢峰—米勒图。本文中以下的图都与下一篇《四色猜测是可以手工证明的》（简称《手工证明》）中的图相同。此处应见《手工证明》一文中图3—1，e和图3—2，e。下同）；以及④任何环形链都不含的（图2—3，c和图2—3，d）；共四种（如图2—3）。图中只要顶点6和顶点7之间不是直接相邻时，图就成了可以同时移去两个同色B的K—构形，而不是H—构形了。
在H—构形中，A—C链和A—D链是连通的，不能交换，因为它空不出颜色，所以A，C，D三种颜色均不可能空出来给待着色顶点V；B—C链和B—D链又不能同时交换，所以也不能空出B给待着色顶点V。但可以想办法破坏连通的A—C和A—D链，使其成为不连通的，使构形变成K—构形而可约。
2、1、2  含有A—B环形链的构形，A—B环必然把C—D链分成环内、环外互不连通的两部分（如图2—3，a），交换环内、环外的任一部分C—D链，都可以使A—C和A—D链断开。使构形变成为不含有连通的A—C和A—D交叉链，又可以同时移去两个同色B的K—构形（图2—3，a就可以变成这种构形，具体操作见《手工证明》一文中的图3—5）。这种情况与含有A—B环形链的“九点形”（如图2—2，a或图2—3，a中去掉小黑点顶点后的图）构形则是不同的。这里的含有A—B环形链的构形是不能移去两个同色B的，而“九点形”构形则是可以同时移去两个同色B的构形。所以这种含有A—B环形链的“九点形”构形是属于K—构形一类。

2、1、3  含有C—D环形链的构形，C—D环也必然把A—B链分成环内、环外互不连通的两部分（如图2—3，b），交换环内、环外的任一部分A—B链，也都可以使A—C和A—D链断开。使构形变成为不含有连通的A—C和A—D交叉链，但又不可以同时移去两个同色B的K—构形，或者也可以同时移去两个同色B的K—构形（图2—2，d和图2—3，b都可以变成这种构形，具体操作见《手工证明》一文中的图3—6）。赫渥特图就是这样着色的。这就是赫渥特图型的H—构形。这种情况与含有C—D环形链的“九点形”构形（如图2—2，d或图2—3，b中去掉小黑点顶点后的图）的解法是相同的，用的都是断链法。所以这种含有C—D环形链的“九点形”构形却是一个H—构形。
2、1、4  既含有A—B环形链，又含有C—D环形链的构形（图见《手工证明》一文中的图3—1，e和图3—2，e），既可以交换A—B环内、外的任一条C—D链，也可交换C—D环内、外的任一条A—B链，都可以使构形变成为K—构形。敢峰—米勒图就是这样着色的，所以敢峰—米勒图是一个H—构形。这种构形，可以单独成为一类，也可以归入以上图2—3，a和图2—3，b两类中的任一类中，因为该图具有以上两类构形的特点，解决办法又是用其中任一种的解决办法都可以，所以不单独列为一类也是可以的。
2、1、5  这里虽然也用的是坎泊的颜色交换技术，但其交换的目的却不是空出颜色，而是“断链”，这就是坎泊的颜色交换技术的第二种作用——“断链”的作用，所以叫“断链交换”。这种交换并不是为了空出颜色给待着色顶点，而是为下一步空出颜色的交换作好技术上的准备。
这种断链交换可以是从非围栏顶点（即非5—轮的轮沿顶点）开始的，交换的链中不含有5—轮的轮沿顶点，如图2—2，d和图2—3，b从顶点8A开始的A—B的交换,以及图2—3，a从顶点6C（或7D）开始的C—D链（边）的交换；也可以从5—轮的轮沿顶点开始，但交换的链中至少含有两个以上的顶点是5—轮的轮沿顶点，如图2—2，d和图2—3，b从顶点2A开始的A—B链的交换，以及图2—3，a从从顶点4D（或5C）开始的C—D链（边）的交换。
2、1、6  在H—构形中，唯独不含A—B和C—D任何一种环形链的构形（如图2—3，c和图2—3，d）是不能用这种“断链”的方法处理的，这就是张彧典先生的第八构形[2]，我们叫它Z—构形，因为它是类似于张彧典先生的第八构形型的H—构型。
2、2  Z—构形
2、2、1  Z—构形的特点：在不含任何环形链的H—构形——Z—构形中，A—C链和A—D链都是连通链，不能交换；A—B链和C—D链也都是直链，且只有一条，也不能交换。即就是交换了，也只等于整个链中的两种颜色互换了一下位置，不起任何作用；B—C链和B—D链又不能同时交换。那么我们就只有先交换一个关于B的链。
2、2、2  转型交换：从任一个同色顶点B进行交换时，5—轮构形的类型就会发生改变：若从顶点1交换了B—D链，构形就由原来的123—BAB型变成了451—DCD型（图见《手工证明》一文中的图3—7）；若从顶点3交换了B—C链，构形则也由原来的123—BAB型变成了345—CDC型（图见《手工证明》一文中的图3—8）。虽然也是在进行坎泊的颜色交换，但交换的目的却是在于使构形进行转型，所以把这种交换叫做“转型交换”。注意，这种转型的交换也是从围栏顶点开始的，并且必须是从两个同色B中的一个同色顶点B开始的。
2、2、3  从“九点形”构形看，不含任何环形链、但可以同时移去两个同色B 的构形（如图2—2，b和图2—2，c）与H—构形（如图2—2，d）是可以相互转化的；而Z—构形与“九点形”中可以同时移去两个同色B的构形又有相同的特点，即A—B链和C—D链都是直链且只有一条，它一定也应是可以转化为类似b类的H—构形的。理论和实践都已经证明了这一点是正确的（因为Z—构形的最简模型是一个“十五点形”，其中就有一个只缺少一个B色顶点的A—B圈，当从顶点1（或3）交换了B—D（或B—C）后，正好就使得这一缺少得到了弥补，该顶点正好就变成了B，构形变成了一个451—DCD（或345—CDC）型的有A—B环形链的类似b类的H—构形。（图见《手工证明》一文中的图3—10），证明了Z—构形是可以通过转型交换转化成为赫渥特图型的H—构形的。这是一个必然的结果，而并非偶然；另外，实践和理论也能证明，Z—构形还可以通过与以上的交换是相反方向的转型交换后，可以直接转化成为可以同时移去两个同色C或D的K—构形（图见《手工证明》一文中的图3—9）。总之，这都说明了Z—构形是可以转化为K—构形的，是可约的。
2、2、4  到此，坎泊的颜色交换技术的三种作用都已经设及到了。现在还要说的一点是：当图是可以同时移去两个同色B的构形时，一定是要进行两次交换才能达到同时移去两个同色B的目的。第一次交换是属于转型交换，把123—BAB型的构形转化成为451—DCD型的构型，或者转化成为345—CDC型的构形，而第二次交换则是属于空出颜色的交换。空出来的颜色B对于原来123—BAB型的构形来说，是两个同色的B，而对于新的构形类型来说，则是非两个同色C或D之外的B。
到此，我们也就证明了所有的5—轮构形都是可约的。
3、四色猜测是正确的
到此，平面图的所有不可免的构形都是可约的了，当然平面图的四色猜测也就是正确的了；平面图的顶点着色又相当于是对地图的面在染色，这也就证明了地图的四色猜测也是正确的；这就证明了四色猜测是正确的。

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

注：此文已于二○一七年元月十一日在《中国博士网》上发表过，网址是：
原文是以与张彧典先生交换意见的形式出现的，这次录用时去掉了与张先生交换意见的部分，并对保留部分的文字稍作了修改，也增加了图。

（未完，接下贴）

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，