四色猜测的再证明 ——回答张彧典先生提出的问题

雷明85639720

四色猜测的再证明
——回答张彧典先生提出的问题
雷  明
（二○一七年十二月二十三日）

张彧典先生提出我对我的H—构形集的解决方法中，所用坎泊交换次数的上线能否证明的问题。我回复说，第一，我不仅用我的构形分类原则及各类构形解决的办法，对张先生的H—构形集中的任何一个构形都能4—着色，而且交换的次数均不大于3：第二，我还能从理论上对其进行证明，并已在网上发表了。现在我重新进行修改，完善，重新发表出来，给张先生朋友演示一番。

1、对5—轮构形来说，连通链A—C和A—D只有共同的起始顶点2A，中途再无交叉顶点时，就是坎泊已经证明过的都是可约的K—构形（如图1，a）；而连通链A—C和A—D不仅有共同的起始顶点2A，而且中途还有别的交叉顶点A时，就是坎泊还没有证明是否可约的赫渥特构形（H—构形）（如图1，b）。
2、解决H—构形的着色问题，主要就是要想办法把连通的A—C链和A—D链的一条，或者两条者断开，使其变得不连通，使构成为K—构形而可约。以下就来专门谈如何使A—C链和A—D链断开的问题。
3、单条链断开：即只断开一条连通链就可以使问题得到解决。
①  若在A—C（或A—D）链中有某一个顶点A，它是一个轮沿顶点着有C、D二色的4—轮的中心顶点时（如图2，a），则把这个顶点的颜色由A换成B（也即是进行A—B链的交换），就可以使连通的A—C链或A—D链的一条或两条断开；

②  若在A—C（或A—D）链中有某一个顶点C（或D），它是一个轮沿顶点着有A、B二色的4—轮的中心顶点时（如图2，b），则把这个顶点的颜色由C（或D）换成D（或C），也就可以使连通的A—C链或A—D链的一条或两条断开。
张先生的第八构形，第七构形等图中也都存在着这样的4—轮，也都可以这样直接的解决问题。
4、两链同时断开：即进行一次某种交换，就可以使两条连通链同时断开，问题也就得到解决。若以上3中的两种4—轮都不存在时，但：
①　构形中又存在经过1B—2A—3B三个顶点的A—B环形链时，4C—5D两个顶点一定会被隔在环形的A—B链的外面（如图3，a），这时，交换A—B环内、外的任一条C—D链（如交换4D—5C链），都可以使两条连通链的A—C链和A—D链同时断开，使构形成为K—构形而可约（如图3，b）。这就是我的a类H—构形。当图是九点形时，就变成了图3，c，这就是张先生的Z1—构形，是可以同时移去两个同色B的构形；


②　或者构形中存在经过4D—5C两个顶点的C—D环形链时，1B—2A—3B三个顶点也一定会被隔在环形的C—D链的外面（如图4，a），这时，交换C—D环内、外的任一条A—B链（如交换1B—2A—3B链），也都可以使两条连通的A—C链和A—D链同时断开（如图4，b）。这就是我的b类H—构形。当图是九点形时，就变成了图4，c，这就是张先生的第二构形，其解决办法也是交换环形的C—D链内、外的任一条A—B链，把图变成K—构形。
敢峰—米勒图中含有经过1B—2A—3B三个顶点的A—B环形链，但不含有经过4D—5C两个顶点的C—D环形链，所以它只能是属于a类形，而不是b类构形。解决时也只能是交换A—B环形链内、外的C—D链，而不能交换C—D环形链内、外的A—B链。这也就是张先生的Z—换色程序的操作。由于A—B链和C—D链是两条相反的色链，是不能相互穿过的，所以，即就是同一个图中有A—B环形链和C—D环形链同时存在，两链也是不会相交叉的，而只能是相离的同心园式的分布状态。

5、构形转型的方法：若以上4中的两种环形链也都不存在，A—B链和C—D链都是直链时，就是我的c类H—构形。这种情况下，必须对构形进行转型，才能使问题得到解决。张先生的第八构形就是这种构形。这种构形有两种情况，如图5所示。
由于图5中的两种情况只是图的左右分布有所不同，其实际上是同一类构形。所以我们只要研究其中之一（如图5，a）就可以了。这两个图，A—C链，A—D链，是连通链，不能交换；A—B链，C—D链是直链，也不能交换；B—C链和B—D链又不能同时交换，那么就只有先交换B—C链和B—D的其中之一，使构形转型，然后再解决转型后的构形。


①　对图5，a先从顶点1交换B—D链，若不能生成从3B到5C的B—C链时（图6，a），再从顶点3交换B—C链，就可以同时移去两个同色B（如图6，b），共两次交换；若从从顶点1交换了B—D链后，可以生成从顶3到顶点5的B—C链时（如图7，a中的虚线所示），则是不可以同时移去两个同色B的。但是，现在转型后的图7，a，却是一个451—DCD型的、可以同时移去两个同色D的构形。先从顶点4交换D—A链（如图7，b），再从顶点1交换D—B链，就可移去两个同色D（如图7，c），共计三次交换；
②　若对图5，a先从顶点3交换B—C链时，则得到一个345—CDC型的、有A—B环形链的b类H—构形（图8，a）。交换环形链A—B内、外的任一条C—D链，都可以使构形变成K—构形而可约（如图8，b），也是最多只用三次交换。

③　若对图5，b先从顶点1交换B—D，图则转化成为一个b类H—构形，若对图5，b先从顶点3交换B—C，图则转化成为一个可以同时移去两个同色C的K—构形。正好与图5，a的转化相反。
张先生的第4到第7构形，除了先从顶点3进行B—C链的交换，再从顶点1进行B—D链的交换，可同时移去两个同色B外，也可以采用对c类构形的解决办法，也是最多只用三次交换就可以解决问题。
张先生的第八构形就可用这种方法进行解决，从一个方向进行颠倒时，得到一个可以同时移去两个同色C或D的K—构形，而从另一个方向进行颠倒时，则可得到一个b类H—构形。
图5若是九点形时，就变成了张先生的构形1和构形3，是两个可以同时移去两个同色B的K—构形（如图9）。

6、从以上的图中可以看出，在有经过1B—A2—3B三个顶点的A—B环形链的图3中，至少1B—A2—3B这三个顶点是以图的对称轴为轴对称分布的；在有经过4D—5C两个顶点的C—D环形链的图4中，至少4D—5C这两个顶点也是以图的对称轴为轴对称分布的；但在无任何环形链的图5中，A—B链和C—D链的分布却都不是对称的。而在没有任何环形链的图中，有没有对称的图呢，也有。如图10，a，但这个图却是一个可以同时移去两个同色B的K—构形。

7、最近，张先生介绍了美图一个人的文章，其中有一个图11，其对偶图比以上的图10要复杂一些（如图11，a）。这也是一个与图10，a类似的构形，其中的A—B链和C—D链都不是环形的，但却是左右对称得非常好。这个图需要三次同方向的颠倒（交换）（逆时针方向颠倒如图11，b，图11，c，图11，d）后，才能转变成为b类H—构形，前两次颠倒构形仍是c类构形，没有进行转化。到最后解决问题时，共计需要五次交换（图11，e，图11，f）。这是一个极特殊的情况。


这个图无论从那个方向颠倒，都是如此。顺时针方向颠倒的过程如图12，a，图12，b，图12，c，图12，d，图12，e，图12，f。




同样都是c类构形，为什么交换的次数却不同呢，原因就在于图的对称性上。图9的图中A—B链和C—D链都是不对称的，所以同一个图从两个不同的方向进行颠倒时，就会产生两种不同类型的构形：一种是变成可以同时移去两个同色的K—构形，另一种则仍是H—构形的b类H—构形。都只要交换三次就可以使问题得到解决。而图11，a的图中A—B链和C—D链都是对称的，所以就产生了从两个不同的方向进行颠倒时，每次交换的结果都是相同的：前两次颠倒得到的都仍是c类的H—构形，第三次颠倒后，才都得到了b类的H—构形。再通过两次交换，最后才解决了问题。
由此可以得出结论：A—B链和C—D链都不对称时，从不同方向的颠倒的结果是不同的；而当A—B链和C—D链都是对称的时，从不同方向颠倒的结果则是相同的。A—B链和C—D链对称时的交换次数比不对称时的交换次数只多两次，但这所多的两次交换正好是两次转型交换未起转型作用的两次，除去这两次不起作用的交换，总的能起作用的交换次数仍然还是三次。
在c类构形中，由于A—B链和C—D链的对称与不对称的原因，构形解决的办法也不相同，所以说，在c类构形中把A—B链和C—D链都对称的构形和都不对称的构形分别作为两类看待也是可以的。

图10，a的图虽是对称的，但只能走同时移去两个同色的解决道路，而不能按一个方向的多次颠倒。否则，从第二次颠倒开始，就会变成总是分别从同一条连通链的两个端点对该链进行的无穷循环的交换，永远不能使问题得到解决（如图13）。图13是按逆时针方向进行的颠倒，一次颠倒后，图成为一个451—DCD型的构形（如图13，b）；第二次逆时针颠倒实质上就是对图13，b从顶点4到顶点2进行的D—A连通链的交换（如图13，c），构形由451—DCD型变成了451—ACA型；再次进行逆时针颠倒时，交换的则还是顶点4到顶点2的A—D连通链（如图13，d），构形（图）又回到了原来图13，b的451—DCD型。再交换，又会开始新一轮的循环。
由此看来，含有A—C和A—D两条连通且相交叉的链的图，在可以同时移去两个同色B时，就必须首先采用同时移去两个同色B的解决办法，不能使用颠倒法。否则，就真的会出无穷现循环的现象。所以我仍建议把只要是能够可以同时移去两个同色B的图，不管其中是否含有A—C和A—D两条连通且相交叉的链，都定义为K—构形；除此以外的所有含有A—C和A—D两条连通且相交叉的链的图，才定义为H—构形是最为科学的。排除了象图10这种对称的、可以同时移去两个同色B的图，H—构形中就不会再出现这种无穷循环现象的图了。
8、还是同一个美国人，还有一个图12，它的对偶图也是一个对称性非常好的图（如图14，a），但这个图也是一个可以同时移去两个同色B的K—构形，而不能进行颠倒。否则也会成为无穷的循环交换，得不到结果（如图14，b，图14，c和图14，d）。




对图14，a用顺时针颠倒也可以得到同样的结果，说明把含有A—C和A—D两条连通且相交叉链的、又可以同时移去两个同色B的构形，统统都不列入H—构形，而统统都看作是K—构形还是正确的。对于这类构形，只能先采用同时移去两个同色B的方法进行解决，而不能采用颠倒的方法。否则，就出现了在同一条连通链间进行无穷次的循环交换了。
由于图14，a中还有两个环形的C—D圈（如图中的加粗边），把A—B链分成了好几部分，交换其中任一部分A—B链，都可以使连通的A—C链和A—D链中的一条或两条断开，使图变成为K—构形而可约。这里就不再画图了，请读者自已画一画。
我这里也请张先生用你的颠倒法把图10，a和图14，a两个图着一下色，看看把这两个图应归入你的九个构形中的那一个。
9、现在，再把我过去文章中对各构形的证明抄录如下：
我的构形有四个图（如图14），但实际上只是三类，其中有两个图是A—B链和C—D链是一左一右不对称分布的构形，应属于同一类（没有画出A—B链和C—D链左右对称的构形）。其可约性的证明如下：

①　有A—B环形链的构形通过断链交换可转化成K—构形的证明：
因为在图14，a中，连通的A—C链和A—D链至少有4D与5C两个顶点是直接相邻的，所以，无论经过1B—2A—3B的A—B环形链是从哪个地方穿过A—C链和A—D链的， A—B环形链的某一侧至少是存在着4D与5C这两个顶的。交换4D与5C的C—D链，就可以使A—C链和A—D链两条连通链同时断开，使构形转化成K—构形。
②　有C—D环形链的构形通过断链交换可转化成K—构形的证明：
因为在图14，b中，连通的A—C链和A—D链至少有顶点2A和顶点8A是两条链的公共顶点（如果没有这两个公共顶点，图也就不可能再是H—构形了），所以，无论经过4D—5C的C—D环形链是从哪个地方穿过A—C链和A—D链的，C—D环形链的某一侧至少也是存在着2A这个顶点的。交换1B—2A—3B的A—B链，也就可以使A—C链和A—D链两条连通链同时断开，使构形转化成K—构形。
③　无环型链的H—构形可以转化成可以同时移去两个同色的K—构形的证明：

对图14，c中的构形从1B施行了一次逆时针转型交换后得到图15，a，是一个451—DCD型的5—轮构形。图15，a中C—A链和C—B链的交叉顶点是6C（即图中加大的顶点），5—轮轮沿顶点中用了两次的颜色是D，从6C到4D有一条C—D链（即图中加粗的边链）；当从顶点4交换了D—A后，生成了从2A到4A的A—C连通链（如图15，b中加粗的边链），使得从顶点1D到3B不可能再有连通的D—B链，从而可以再从1D交换D—B，同时移去两个同色D。这就证明了图14，c的无环形链的H—构形是一定可以转化成为可以同时移去两个同色D的K—构形的。对图14，d的构形从3B施行了一次顺时针转型交换后，得到的345—CDC型的5—轮构形，也有同样的结果，也是可以同时移去两个同色C的K—构形。
④　无环形链的H—构形可以转化成类赫渥特图型的H—构形，再转化成坎泊的K—构形的证明：

在图14，c（或图14，d）的构形中，有通过顶点2A—1B…8A—6C—2A（或2A—3B…8A—7D—2A）的、且有缺口是6C（或7D）的A—B圈（见图16，a中加粗的边链），当对图14，c从顶点3交换B—C（或对图14，d从顶点1交换B—D）时，顶点6C变成了6B（或顶点7D则变成了7B），就形成了一条完整的环形的A—B链（见图16，b中加粗的环形链），把C—D链分成了环内、环外互不连通的两部分，构形具有了b类构形的特点了。是一个345—CDC型（或451—DCD型）的类赫渥特图型的H—构形，一定是可以转化为K—构形的。
10、到此，就可以说明四色猜测是正确的。
在以上的研究中，主要是针对H—构形的，因为K—构形早在一个半世纪之前已由坎泊证明了都是可约的。我们在这里的证明中，首先从解决切断连通的A—C链和A—D链入手，解决了如何断开一条连通链的问题，也解决了如何同时断开两条连通链的问题。
在同时断开两条连通链中，我们在可交换的A—B链和C—D链中，研究了A—B链和C—D链分别呈环形链的情况，构形都是可约的。
在A—B链和C—D链都不呈环形链，不能断开任何一条连通链，且在B—C链和B—D链又只能交换一条的情况下，又研究了转型交换法。分别交换B—C链和B—D链中的一种，使构形类型发生转化，得到转化后的新型构形也都是可约的。
从图的左右对称性方面，我们研究了对称的构形，又研究了不对称的构形，他们也都是可约的。
从解决的方法上看，对称与不对称的构形，断开一条连通链和同时断开两条连通链，以及不能断开任何一条连通链的情况下，各种情况解决的办法也是各不相同的。这充分反映了我们在对构形的分类中，所采用的“结构不同，解法不同”的分类原则是正确的。我们的H—构形的不可免集是完备的。
不可免集是完备的，其中的各个不可免构形也都是可约的，当然也就说明了四色猜测是正确的。


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

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

雷明85639720

,,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，