用着色法证明四色猜测时首先要研究平面图的不可免集

雷明85639720

用着色法证明四色猜测时首先要研究平面图的不可免集
雷  明
（二○一八年十月八日）

平面图有无穷多个，不可能对每一个平面图都进行着色，看其是否可以4—着色。首先必须把这个无穷的问题转变成一个有穷的问题。所以坎泊就提出了“构形”的概念。构形就是只有一个顶点未着色（即待着色顶点），而其他顶点都着上了四种颜色之一且符合着色要求的图。解决四色问题也就是要解决各构形的待着色顶点的着色问题。构形在表示时一般只画出待着色顶点和与其相邻的顶点，其他的顶点可以略去不画。所以构形在一般情况下表现的只是一个轮形图。轮的中心顶点就是待着色顶点，而轮的轮沿顶点就叫构形的“围栏”顶点。
因为在一般的情况下研究的都是极大的平面图（极大平面图就是地图的对偶图，极大图的顶点就是地图中的面或区域），而极大平面图的每一个顶点和与其相邻的顶点都够成了一个轮构形。但轮构形的围栏顶点也可以无穷多的，所以说轮构形也是无穷多的。但可以证明任何平面图（包括极大的平面图）中都一定含有至少一个度小于等于5的顶点。这就为把一个无限的问题转变为一个有限的问题提供了方便。只要证明小于等于5的有限个轮构形都是可4—着色的，即坎泊所说的“可约”的，则四色猜测也就可以得到证明是正确的。这一步是把对无穷多的图和无穷多的轮构形的着色问题，转化成了只是对有限多的小于等于5的轮构形的着色问题了。
在用四种颜色已经着过色的构形的围栏顶点以外的顶点中，一定存在着各种不同的由两种颜色交替着色的顶点序列。在研究四色问题中，往往把这样的序列叫做“色链”，简称“链”。在小于等于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—构形中的相互关系只可能是：①只有一条经过待着色顶点三个围栏顶点的环形的A—B邻角链的构形，②只有一条经过待着色顶点两个围栏顶点的环形的C—D邻角链的构形。③任何环形邻角链都没有的构形，和④两种环形邻角链都有的构形四种情况。而第④种情况又分别属于第①和第②两种情况，所以可以不再单独列项。实际上以上两种相反的邻角链的相互关系，只有①②③的三种情况。这三种情况的构形就是H—构形的不可免集，且是完备的不可免集。至此，就又把对无穷多的H—构形的着色问题，转化成了只对三个类型的有限多的H—构形的着色问题了。
证明了H—构形的这三种类型的不可免的构形是可约的时候，也就是四色问题得到解决的时候，这时，就可以得出四色猜测到底是正确还是错误的结论。
我们已多次证明了这三种情况下的H—构形都是可约的，所以说四色猜测是正确的。这里也就不再多说了。况且我们本文的目的并不是在于研究解决这三类构形的可约性问题的，而是在于研究解决如何把一个无限的问题变成一个有限的问题来进行解决的问题的。

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

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