可约构形法证明四色猜测

雷  明

（二○一八年元月二十二日）

1、 构形与H—构形

证明四色猜测时，人们一般都喜欢用可约构形法进行证明。但可约构形法是一种着色的方法，使用该方法时，就必须把无限的平面图，划归为有限的几个不可免构形，才能把一个无限的问题转化为一个有限的问题。只要证明了这些构形是可约的（即是可4—着色的），四色猜测就被证明是正确的了。坎泊早已把地图（无割边的3—正则平面图）划归为四类构形，即一国与两国相邻，一国与三国相邻，一国与四国相邻，一国与五国相邻，四种构形；对于平面图来说，就是0—轮构形，1—轮构形，2—轮构形，3—轮构形，4—轮构形，5—轮构形六种。

坎泊已用可空出颜色的交换技术，证明了一国与两国相邻，一国与三国相邻，一国与四国相邻，一国与五国相邻的一部分，即0—轮构形，1—轮构形，2—轮构形，3—轮构形，4—轮构形，5—轮构形的一部分，都是可约的。这就是K—构形；而对一国与五国相邻或5—轮构形的另一部分则未证明是否可约，即既不能空出A，C，D三色之一（因为图中有连通的A—C链和A—D链，不可交换，也就空不出颜色），也不能空出两个同色B（因为图中从一个1B或3B交换了B—D或B—C，就会新生成从3B或1B到5C或4D的连通链B—C或B—D，也就不可同时移去两个同色）的构形，却未能证明其是否可约。这就是赫渥特指出的坎泊证明中的“漏洞”所在。这就是H—构形。

这时要特别强调的是：连通的A—C链和A—D链的相互交叉，虽是构成H—构形的必要条件，但不是充分条件。有了这个条件的图，虽不能空出A，B，C三色之一，但却不一定也都不可移去两个同色B。如图1中的几个图。还有图2和图3等图，都是可以同时移去两个同色B的。所以构成H—构形的条件，还必须再加上不能同时移去两个同色B的条件。

http://s10/mw690/001MUq8Tzy7hzEjvEAFf9&690

    2、 H—构形可约性的证明

H—构形中，A—C链和A—D链不能交换，空不出A，C，D来，B—C链和B—D链又不能同时交换，也空不出B来。现在剩下可交换的链就只有A—B和C—D了。这两条链又是相反链，不能相互交叉。所以这两种链在图中的关系只能是：有了经过1B，2A，3B三个顶点的环形的A—B链，就不可能再有经过4D和5C两个顶点的环形的C—D链，反之亦然，或者就是这两种环形链一条也没有，两链都是直链。

http://s6/mw690/001MUq8Tzy7hzEkI777f5&690
http://s8/mw690/001MUq8Tzy7hzElrZKT07&690

2、1  H—构形的4—着色

第一种情况，当图中有经过以上1B，2A，3B三个顶点的环形的A—B链时（如图4，a），它一定把C—D链分成了不连通的两部分，至少可以交换经过4D和5C的C—D链，一定可以使连通的A—C链和A—D链同时断开，使图成为K—构形而可约。这种情况的图我们叫做a类H—构形。

第二种情况，当图中有经过以上4D和5C两个顶点的环形的C—D链时（如图4，b），它也一定把A—B链分成了不连通的两部分，至少也可以交换经过1B，2A，3B的A—B链，也一定可以使连通的A—C链和A—D链同时断开，使图成为K—构形而可约。这种情况的图我们叫做b类H—构形。

http://s5/mw690/001MUq8Tzy7hzEmYjdO64&690

    以上两种方法都是让原来连通的A—C链和A—D链断开，所以叫做断链法，相应的交换也就叫断链交换。

第三种情况，当以上两种环形链都不存在时（如图4，c和图4d），这时，A—B链和C—D链也不能交换了，就只有交换一个关于B的链，使图转型了。当交换了一个关于B的链时，图就会转化成DCD型或CDC型的可以同时移去两个同色的K—构形，或者转化成以上第二种情况的b类构形，最后都是可约的。由于这种交换的目的是为了使构形转型，所以我们叫它转型法，相应的交换也就叫转型交换。

2、2  H—构形可约性证明

第一种情况，因为4D和5C是A—D链和A—C链的末端顶点，其颜色变了，该链也就断开了。敢峰—米勒图就是这种情况的图，敢峰先生1992年出版的《证明四色定理的新数学——图论中的锁阵运筹》一书中就是用这种方法对敢峰—米勒图进行4—着色的，所以敢峰—米勒图是a类H—构形；

第二种情况，因为2A是A—D链和A—C链的共同起点，其颜色变了，该链也就断开了。赫渥特图就是这种情况的图，雷明先生1992年在陕西省数学会第七次代表大会暨学术交流会上所作的学术论文报告“赫渥特图的4—着色”中就是用这种方法对赫渥特图在赫渥特原着色基础上进行4—着色的，所以赫渥特图是b类H—构形。

第三种情况证明之一，可以转化成可以同时移去两个同色的K—构形的证明：对图5，a（图5，a和图5，b是图4，c和图4，d的另一种画法）中的构形从1B施行了一次逆时针转型交换后得到图6，a，是一个451—DCD型的5—轮构形；

http://s7/mw690/001MUq8Tzy7hzEp4wDAc6&690
http://s10/mw690/001MUq8Tzy7hzEpRVkR19&690
 

图6，a中C—A链和C—B链的交叉顶点是6C（即图中加大的顶点），5—轮轮沿顶点中用了两次的颜色是D，从6C到4D有一条C—D链（即图中加粗的边链）；当从顶点4交换了D—A后，生成了从2A到4A的A—C连通链（如图6，b中加粗的边链），使得从顶点1D到3B不可能再有连通的D—B链，从而可以再从1D交换D—B，同时移去两个同色D。这就证明了图5，a的无环形链的H—构形是一定可以转化成为可以同时移去两个同色D的K—构形的；

对图5，b的构形从3B施行了一次顺时针转型交换后，得到的345—CDC型的5—轮构形，也有同样的结果，也是可以同时移去两个同色C的K—构形。

http://s5/mw690/001MUq8Tzy7hzErIFj6d4&690
http://s3/mw690/001MUq8Tzy7hzEsCocW52&690
 

第三种情况证明之二，可以转化成b类H—构形，再转化成坎泊的K—构形的证明：在图5，a（或图5，b）的构形中，有通过顶点2A—1B…8A—6C—2A（或2A—3B…8A—7D—2A）的、且有缺口是6C（或7D）的A—B圈（见图7中加粗的边链），当对图5，a从顶点3交换B—C（或对图5，b从顶点1交换B—D）时，顶点6C变成了6B（或顶点7D变成了7B），就形成了一条完整的环形的A—B圈（见图8中加粗的环形链），把C—D链分成了环内、环外互不连通的两部分，构形具有了b类H—构形的特点了，一定是可约的了；

图8是一个345—CDC型（或451—DCD型）的分别有经过五边形A—B两个顶点的A—B环形链的b类H—构形，一定也是可以转化为K—构形的。注意，这里图8中的环形A—B链相当于前面4，b中的C—D环形链。

张彧典先生的第八构形就是这种情况的图，雷明先生近几年就是用这种方法给张先生的第八构形进行4—着色的，所以张先生的第八构形是c类H—构形。

2、3  对称性构形的的证明

以上所研究的a类，b类构形中的链对于图的对称轴也都是对称的，而所研究如的c类构形中的链对于图的对称轴却是不对称的，c类构形有没有对称的构形呢，有。如图9，a所示。这个构形在进行转型交换时，前两次交换均没有起到构形转型的作用，仍然是c类构形；到了第三次交换才进行了转型，变成了b类H—构形（如图9，b），比不对称的c类构形解决问题时的交换次数多了两次，这两次正好是不起转型作用的两次交换。该图逆时针方向颠倒和顺时针方向颠倒的结果都是一样的，都需要五次交换，且前两次交换都是不起转型作用的交换。

http://s3/mw690/001MUq8Tzy7hB7eXOZYb2&690

为什么会产生两次不转型的交换呢，就是因为第一次交换后的图仍是一个对图的对称轴是对称的构形（如图10），第二次交换后才是一个对图的对称轴是非对称的构形了（如图11）。因此才有第三次交换后构形发生转型的现象，转型后的图如图9，b所示。

现在，新的问题就提出来了，这个对称的c类构形解决问题时比非对称的c类构形的交换次数多了两次，且这两次正好是不起转型作用的两次交换。那么类似于图9，a的图在解决问题时，是否都会有两次不起转型作用的交换呢。这个可不一定。但这个不起转型作用的交换次数有没有一个上界呢。可以肯定的说，应该是有的。这个上界是可以证明的，且是有限的。

http://s12/mw690/001MUq8Tzy7hB7gfMXp8b&690
http://s15/mw690/001MUq8Tzy7hB7h6qdM7e&690
 

我们知道，一个5—轮的H—构形进行同方向的转型交换，要彻底使图中各顶点（特别是5—轮的5个轮沿顶点）所着的颜色要返回到最初始的着色状态，图与最初始时又是相同的构形类型时，总共要交换20次。解决问题一定只会在这20次交换之内，绝对不会在交换的次数大于20之后才得到解决。这20次交换之内一定会有某次交换是起了转型作用的，事实也已证明了这一点，的确各类构形的交换次数是远小于20次的，只有这个图9交换的次数稍多一点，但也只有5次，仍远小于20次。所以这个不起转型作用的交换次数的上界就应是19－3＝16（其中的3就是起到了转型作用的那次交换，与解决b类构形的两次交换的总和）。这就是说，这种图在解决问题时，最多只需要交换19次，不起转型作用的交换最多只可能是16次。

 2、4  非对称性含有A—B或C—D环形链的构形可约的证明

有没有非对称性的含有环形的A—B链或C—D链的构形呢，有。张先生《探秘》书中的图8.1就是一个例子（如图12），不过这里的A—B环形链是不经过1B，2A，3B三个顶点的， C—D环形链也是不经过4D和5C两个顶点的，否则，若经过了就成为对称的环形链了。

http://s2/mw690/001MUq8Tzy7hCJcNmG521&690

图12中有一个着有C、D二色的4—圈（即非对称的C—D环形链）交换其中的A—B链（即改孤点A为B），就可以使一条连通的A—C链断链，图成为可约的K—构形；图12中还有一个着有A、B二色的4—圈（即非对称的A—B环形链）交换其中的C—D链（即改孤点D为C），就可以使另一条连通的A—D链断链，图成为可约的K—构形。当然最根本的方法还是按解决c类构形的转型法了。

类似于图12中位于连通链A—C或A—D上的着有C、D二色的4—圈和着有A、B二色的4—圈的情况还有张先生的第四到第八构形。第八构形（如图13）、第七构形（如图14）和第六构形（图就不画了）中都含位于连通链A—D上的着有B、D二色的4—圈；第五构形和第四构形中都含有位于连通链A—D上的着有A、B二色的4—圈（图也就不画了）。他们都可以交换圈内孤点的颜色，使一条连通链断链。

http://s1/mw690/001MUq8Tzy7hCJe6EHS50&690
http://s16/mw690/001MUq8Tzy7hCJeHVhB0f&690

当然了，这里所说的4—圈却不一定都是4—圈，也可能是其他的偶圈，圈内的孤点也可能不是孤点，而是一条寄道路。

除了以上的三种情况外，再也没有别的情况了。所以H—构形只有以上a，b，c三种不可免构形，且都是可约的。证毕。 

H—构形都是可约的，加上坎泊已证明过的可约的K—构形，现在平面图的所有不可免的构形都是可约的了，这就证明了四色猜测是正确的。

雷  明

二○一八年元月二十二日于长安

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

http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=3525