解决四色问题的关键是一定要把无穷的问题转化成有穷的问题

雷明85639720

解决四色问题的关键是一定要把无穷的问题转化成有穷的问题
——四色猜测的一般性证明方法
雷  明
（二○一八年十月十五日）

1、把一个无穷问题转化成一个有穷的问题
平面图有无穷多个；一个平面图的顶点个数也是任意的，也可以有无穷多个；一个平面图中的任何一个顶点的度也是任意的，也可以说是可无穷大的；而且在一个平面图中，顶点间的相邻关系也是任意的，是极其复杂的。我们不可能对每一个平面图都进行着色，看其是否可以4—着色，而且是永远也着不完的。为此，就必须首先把这个无穷的问题转化成一个有穷的问题。所以坎泊就提出了“构形”的概念。
构形就是只有一个顶点未着色（即待着色的顶点），而其他顶点都已着上了四种颜色之一，且符合着色要求的图。解决四色问题也就是要解决各种构形的待着色顶点的着色问题。构形在表示时一般只画出待着色顶点和与其相邻的顶点，其他的顶点可以略去不画。所以构形在一般情况下表现的只是一个轮形图。轮的中心顶点就是待着色顶点，而轮的轮沿顶点就叫构形的“围栏”顶点。
因为在一般的情况下研究的图都是极大的平面图（极大平面图就是地图的对偶图，极大图的顶点就是地图中的面或区域，给地图的区域或面的染色就是对其对偶图的顶点着色，这就把一个地理问题转化成了一个数学问题了），而极大平面图的每一个顶点和与其相邻的顶点都构成了一个轮构形。同样的，轮构形的围栏顶点也可以无穷多的，所以说轮构形也是有无穷多个的。但在图论中，可以证明任何平面图（包括极大的平面图在内）中都一定含有至少一个这样的顶点，其度小于等于5的。这就为把一个无限的问题转化为一个有限的问题提供了方便的条件。只要证明小于等于5的有限个轮构形都是可4—着色的，即坎泊所说的“可约”的，则四色猜测也就可以得到证明是正确的。这就把对无穷多的图和无穷多的轮构形的着色问题，转化成了只是对有限多的小于等于5的轮构形的着色问题了。
2、把无穷多的H—构形转化成有限个不可避免的构形
在用四种颜色已经着过色的构形中，在围栏顶点以外的顶点中，一定存在着各种不同的由两种颜色交替着色的顶点序列。在研究四色问题中，往往把这样的序列叫做“色链”，简称“链”。在小于等于5的轮构形的围栏顶点以外的顶点中，把由围栏的对角顶点的颜色所构成的色链叫对角链；相应的也可把由围栏的相邻顶点的颜色所构成的色链叫邻角链。在证明四色猜测时,可以只画出各链的相互关系，也不必画出构链中所有的顶点。从这一点上说，构形不是一个具体的图。从一个顶点到其一个对角顶点的对角链如果是不连通时，则可以从一个对角顶点开始交换该链中各顶点的颜色，就可以空出一种颜色（即开始交换的顶点的颜色），给待着色顶点着上。
坎泊通过对对角链的简单交换（一次或两次），已经解决了：①无连通的对角链的情况的构形，②只有一条连通的对角链的情况的构形，③有两条有同一起始顶点的连通的对角链，但两链中途不再相互交叉的情况的构形，和④有两条有不同起始顶点的连通的对角链，但在中途又有相交叉顶点的情况的构形，这四种情况下的构形都是可约的。唯独没有解决有两条既有同一起始顶点的连通的对角链，在中途又有相交叉顶点的这一情况下的构形是否是可约的问题。这一情况就是赫渥特指出的坎泊证明中的“漏洞”所在的构形。
把坎泊已经证明了是可约的构形，我们叫它坎泊构形，用K—构形来表示；把坎泊遗漏了的构形，因为是赫渥特发现的，所以我们叫它赫渥特构形，用H—构形来表示。解决四色问题，现在就是要解决H—构形的可约性的问题。在BAB型的H—构形中，因为有连通的A—C链和连通的A—D链，所以是不能空出A，C，D三色之一来的；又由于A—C链与A—D链在中途又相交叉，所以也是空不出两个同色B来的。也就是说H—构形是不能通过对对角链的简单的一、二次交换空出任何一种颜色给待着色顶点的。
同样的，由于H—构形也是有无穷多的，也必须把这个无穷多变成有限的，才能解决问题。构成H—构形的必要条件是，有两条既有同一个起始顶点，在中途又有相交叉顶点的两条连通链。但这并不是充分条件，因为的确有一些已经满足这一必要条件的构形，却是可以连续的移去两个同色B的K—构形。
由四种颜色所能构成的六种色链中，已有连通的对角链A—C链和A—D链不能交换；对角链B—C链和B—D链虽不连通，但也不能连续的进行交换，即就是连续的交换了，也是空不出两个同色B的；六种链中，剩下来的就只有邻角链A—B链和C—D链了；现在就只能考虑这两种链的交换问题了。
这两条链是两条相反的色链，在图中是不可能相交叉的。其在H—构形中的相互关系只可能是：①只有一条经过待着色顶点三个围栏顶点1B，2A和3B的环形的A—B邻角链的构形（如图1），②只有一条经过待着色顶点两个围栏顶点4D和5C的环形的C—D邻角链的构形（如图2），③任何环形的邻角链都没有的构形（如图3和图4），和④两种环形的邻角链都有的构形四种情况。而第④种情况又分别属于第①和第②两种情况中的任何一种，所以可以不再单独列项。实际上以上两种相反的邻角链的相互关系，只有①②③的三种情况。除此之外，这两条链的相互关系就再也没有别的情况了。所以由这①②③三种情况的构形，就构成了H—构形的不可免集，且是完备的。
至此，就又把对无穷多的H—构形的着色问题，转化成了只对三个类型的有限多的H—构形的着色问题了。证明了H—构形的这三种类型的不可免的构形是可约的时候，也就是四色问题得到解决的时候，这时，就可以得出四色猜测到底是正确还是错误的结论。
3、三种类型的不可免的H—构形都是可约的
有一条经过待着色顶点三个围栏顶点1B，2A和3B的环形的A—B邻角链的构形（如图1），我们叫它A类H—构形。A类H—构形中有一条环形的A—B链，把C—D链隔分成两个互不连通的部分，交换经过5—轮的4D和5C两个轮沿顶点的C—D链。就可使连通且相交叉的A—C链和A—D 链变得不连通，使图变成可约的K—构形而可约。
有一条经过待着色顶点两个围栏顶点4D和5C的环形的C—D邻角链的构形（如图2），我们叫它B类H—构形。B类H—构形中有一条环形的C—D链，把A—B链隔分成两个互不连通的部分，交换经过5—轮的1B，2A和3B三个轮沿顶点的A—B链。也可使连通且相交叉的A—C链和A—D 链变得不连通，使图变成可约的K—构形而可约。



任何环形的邻角链都没有的构形（如图3和图4），我们叫它C类H—构形。这两个C类H—构形是左、右结构完全相反的构形，实质上是同一种类的构形。图中没有任何符合上述要求的环形链，且A—B链和C—D链都是直链，且不相交。解决这类构形的办法分别是：
对图3把左上角的一个4—度顶点由C改成B（这相当于在一个环形的A—D链内进行相反色链C—B链的交换），对图4把右上角的一个4—度顶点由D成A（也相当在于一个环形的B—C链内进行相反色链A—D链的交换），两个图就都转化成为如图1的有一条经过待着色顶点三个围栏顶点1B，2A和3B的环形的A—B邻角链的A类H—构形了，自然也就是可约的了。
对图3把右上角的一个4—度顶点由A改成D（也相当在于一个环形的B—C链内进行相反色链A—D链的交换），对图4把左上角的一个4—度顶点由B改成C（也相当于在一个环形的A—D链内进行相反色链C—B链的交换），两个图也就都转化成为如图2的有一条经过待着色顶点两个围栏顶点4D和5C的环形的C—D邻角链的B类H—构形了，自然也就是可约的了。



对转化后的图，分别再按A类和B类的H—构形去解决就行了。如果所改变颜色的4—度顶点位于两条连通的A—C链和A—D链上（如图中的其他四个4—度顶点），则改变该4—度顶点的颜色后，图就直接变成了可约的K—构形。因为其颜色的改变直接就可使A—C链或A—D链变得不连通了。
到此，就证明了三种类型的不可免的H—构形都是可约的。
4、C类H—构形一定可以转化成A类或B类H—构形的再证明
至此，我们虽然已经证明了三类H—构形都是可约的了，但我们还想用转型交换方法，对C类H—构形再试一试。因为图3和图4只是左、右分布上的不同，所以我们只对图3的图进行转型交换就行了。
对图3从顶点1施行了逆时针转型交换后，得到图6。得明显图6中有一条经过了5—轮的2A和3B两个轮沿顶点的环形的A—B链（如图中的加粗边），是一个B类的H—构形，也是可约的。



对图3从顶点3施行顺时针转型交换后，所得到的图7好象是一个可以连续的移去两个同色C的K—构形，但当从顶点5交换了C—A链（这也是一次顺时针转型交换），移去了一个C后，得到的图8中虽然没有从另一个着C的顶点3到顶点1B的连通的C—B链，但却可以在平面图范围内构造出这样的连通链（如图9中的加粗边），使得不可能连续的再移去另一个同色C。图仍旧是一个有两条既有同一个起始顶点1B，同途又有着色为B的相交叉的顶点（如图9中的加大顶点）。



对图9是否还要再施行顺时针转型交换，看其是否还能够转型为A类H—构形，B类H—构形，或直接就得到K—构形呢？我们也就不再继续施行转型交换了。因为按我们的经验，最多施行连续转型交换四次就可以转化成类似以上的A类H—构形，B类H—构形，或K—构形三种构形之一了。但不管怎样，前面已经证明了该构形最后一定是可以转化成K—构形的，这已经说明它是可约的了。（实际上，图9虽然仍有两条相交叉的、且有共同起始顶点的连通链B—C和B—D，但却是一个可以先从顶点2A交换A—D链后，再从顶点5A交换A—C链，就可以连续的移去两个同色A的K—构形（如图10）。或者对图9这个K—构形先从顶点2A交换A—D链后，再从顶点3C交换A—C链，还可以空出C给待着色顶点着上。）

5、 A—B链和C—D链都是轴对称的C类H—构形的解法

以上的研究中，在A类和B类H—构形中的A—B链和C—D链都是轴对称的，而只有C类H—构形中的A—B链和C—D链是非对称的。1935年美国人Irving Kittell构造的地图（如图11，a），就是一个A—B链和C—D链是对称的C类H—构形的代表。图11，b和图11，c都是图11，a的对偶图，只是不同的两种画法而已。两个图中都有A—B链的一部分作A—B链和C—D链的对称轴。解决图11，b这种构形时，必须进行三次同方向的连续的转型交换，才能使图转化为既有经过5—轮的三个轮沿顶点的环形链（如图12，c中的C—D环形链），又有经过5—轮的两个轮沿顶点的环形链（如图12，c中的A—B环形链），既是A类H—构形，又是B—类H—构形的构形。再按A类H—构形或B类H—构形的解决办法去处理即可。总共只需要进行五次交换即可解决问题。

    这种构形当顶点数减少到九点形时，就成了可以连续的移去两个同色B的K—构形了（如图12，d）。
    6、四色猜测的最后证明
到此，就证明了所有的H—构形都是可约的，加上坎泊已经证明了的K—构形也都是可约的，则平面图的所有构形就都是可约的了。四色猜测也就得到证明是可约的。

雷  明
二○一八年十月十五日于长安

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