H—构形的可约性是证明四色猜测的关键

雷明85639720

H—构形的可约性是证明四色猜测的关键
雷  明
（二○一九年四月二十日）
（在这里我发不上图，请到《中国博士网》中去看）

我们在给平面图着色时，总是一个顶点一个顶点的着，总有剩下最后一个顶点的时候。当与这个最后顶点相邻接的顶点数小于等于3，或者与这个最后顶点相邻接的顶点所点用的颜色种数小于于等于3时，该顶点一定是可以着上图中已用过的四种颜色之一的。否则，该顶点该如何着色呢？
我们知道任何平面图中总存在着至少一个顶点的度是小于等于5的。这就是说，我们总可以把最后着色的顶点放在度小于等于5的顶点上。现在就只研究最后顶点的度是4和5的顶点是否可约就可以证明四色猜测是否正确了。
当最后顶点（即待着色顶点）的度是4时，两对对角顶点的颜色构成的色链，可以是连通的，也可以是不连通的；但若有一对对角链是连通的时，另一对则一定是不连通的；因为这两对对角链正好是一对相反链，即两链中的颜色完全不同，是不能相互穿过的。这时，从不连通的对角链的某一个对角顶点起，开始交换该对角链中各顶点的颜色，则该顶点的颜色就变成与其对角顶点相同的颜色了。空出了一种颜色来，可以给待着色顶点着上。图中仍然是四种颜色。这就是坎泊1879年创造的颜色交换技术。从待着色顶点的相邻顶点开始运用交换技术，是可以空出颜色给待着色顶点的。
当然这一颜色交换技术也是可以应用到待着色顶点的度是5的情况的。坎泊1879年已经解决了待着色顶点是5度时，无连通链，有一条连通链，有两条连通链且两链只有一个共同顶点情况下的图是可约的，而遗漏了有两条连通链但两链却有两个以上共同顶点情况下的图是否可约的问题。这一问题在1890年被赫渥特找了出来，所以叫做H—构形。
在H—构形中，A—C链和A—D链是连通的，不能进行交换，空不出A，C，D三色之一；虽然B—C链和B—D链均不连通，但交换了B—C（或B—D）链后，又会新生成连通的B—D（或B—C）链，仍不能连续的移去两个同色B。产生这一情况的原因主要来自于有两以上个共同顶点的两条连通的A—C链和A—D链。那么我们就可以想办法破坏这两条链的连通性，使构形转变成坎泊已经证明了的可约的K—构形。只要能证明各种情况下的H—构形都是可约的，四色猜测也就得到了证明是正确的。
在H—构形中，四种颜色所能构成的六种链中，已有四种不能交换，只剩下A—B链和C—D链是可以交换的。正好该两链中的A，C，D三种颜色的顶点都是连通的A—C链和A—D链中的关键顶点，且处在两链的端点顶点或交叉顶点上。对A—B链或C—D链进行交换，必然破坏A—C链和A—D链的连通性，使构形变成K—构形而可约。
由于A—B链和C—D链正好是一对相反链，所以他们是不可能相交叉的。该两链在图中的分布只能是：①　两种链都是环形链，且两种环形链都经过了构形的围栏顶点，两环的分布不呈同心园（如图１，a，b）；②　两种链都是环形链，且只有一种环形链经过了构形的围栏顶点，两环呈同心园分布（如图２，a，b）；③　只有一种环形链，另一种链是两条不连通的直链，分布在环的内外两侧（如图３，a，b）；④  没有任何环形链的，且两链都是一条直链（即树，如图4，a，b）。

第一种情况，两种环形链不是同心园，各自都经过了自已应该经过的围栏顶点。这种构形交换了环形链内、外的相反链后，都一定会使连通的A—C链和A—D链断开。但一种情况是交换了相反链后，构形成为K—构形而可约；而另一种情况是交换了相反链后，却又新生成了两条有两个共同顶点的连通链，构形仍是H—构形。图1（a）的构形，在A—B环形链内、外交换C—D链，图均变成K—构形而可约（如图5）；在C—D环形链内交换A—B链，与连通链无关，图仍是H—构形（如图6，a）；在C—D环形链外交换A—B链，虽然原有交叉链断开了，但又产生了新的交叉链，图仍是H—构形（如图6，b）。

图1（b）的构形，在A—B环形链内外交换C—D链，图均变成K—构形而可约（如图6—1）；在C—D环形链内外交换A—B链，同样，虽然原有的交叉链断开了，但又产生了新的交叉链，图仍是H—构形（如图6—2）。

第二种情况，两种环形链是同心园，必然有一种环形链是没有经过围栏顶点的。这种构形应以经过了构形围栏顶点的环形链为主环，交换其内、外的相反链，也一定会使A—C链和A—D 链断开，使构形成为K—构形而可约；否则以另一环形链为主环时，交换的结果，虽然原来的连通链也断开了，但却新生成了两条有两个共同顶点的连通链，构形仍是H—构形。图2（a）的构形，在A—B主环形链内、外交换C—D链，图均变成K—构形而可约（如图7）；在C—D副环形链内、外交换A—B链，同样，虽然原有的连通链断开了，但又新产生了两条有两个共同顶点的连通链，图仍是H—构形（如图8）。

图2（b）的构形，在C—D主环形链内外交换A—B链，图均变成K—构形而可约（如图8—1）；在A—B副环形链内外交换C—D链，同样，虽然原有的交叉链断开了，但又产生了新的交叉链，图仍是H—构形（如图8—2）。

第三种情况,只有一种链是环形的,另一种链是两条不连通的直链,且分布在环的两铡。该环内、外的另一种链一定是连通的A—C链和A—D链上的顶点，交换了该环内、外的任一条相反链，都可以使连通的A—C链和A—D链断开，构形变成K—构形而可约。图3（a）交换的结果如图9，图3（b）交换的结果如图10。

以上交换的A—B链或C—Ｄ链，都没有直接从构形的围栏顶点开始，但都是由构形的围栏顶点的邻角颜色所构成的链，都直接使连通的A—C链和和A—D链断开了，所以可以叫做断链交换或邻角链交换。这样相应的就把坎泊从围栏顶点开始的、可以空出颜色的交换叫做空出颜色的交换，或对角链交换。
第四种情况，构形中两种链都是直链，都不可能交换。现在就只能先交换一条关于两个同色B的B—C（或B—D）链，先移去一个B，使构形进行转型。转型分为连续的按逆时针方向或连续的按顺时针方向进行的两种转型。每进行一次转型,构形的峰点发生一次变化，同样的两个同色顶点也在发生着变化。5—轮构形有5个围栏顶点，占用了4种颜色，要使得构形各顶点的颜色，又反回到初始状态的颜色时，每20次转型是一个周期。有没有构形是永远的转型下去，而不能空出颜色来呢？有。图2（a）就是一个例子，这个图是一个无穷转型交换的构形。它虽然永远转型不完，但它的每一次转型的结果，却是一个只有一种经过了应该经过的围栏顶点的环形链的H—构形。交换该环形链内、外的另一种相反链，都可以使图变成K—构形而可约。图2（a）的第二类构形，是一个有两种呈同心园分布的环形链的构形，而我们这里所说的第四类构形，却是没有任何环形链的H—构形。如果这种构形也能够象图2（a）那样，无穷的转型下去，则该图中就应该有两条呈同心园分布的环形链，但它却是一条也没有的。不符合无穷转型构形的条件。所以这种构形，在进行转型交换时，最多进行20次，就一定会变成一个可以连续的移去两个同色的K—构形。
如果一个图是需要20次转型交换的构形，则它的逆向转型交换的次数则是0，一定是可以连续的移去两个同色B的。所以第四类的这种构形的两个方向的转型交换次数的和，也一定是不会大于20次的。一个可以连续的移去两个同色的构形，要空出颜色来，最少还需要进行两次空出颜色的交换。所以任何一个平面图构形最大的交换次数是22次，就可以空出颜色来给待着色顶点的。由于22是一个有限的数字，这就说明了任何平面图，在不大于22次的有限次交换之内都是可约的。这就证明了四色猜测是正确的。

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

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

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，