四色问题证明之三 ——平面图的不可避免构形都是可约的

雷明85639720

四色问题证明之三
——平面图的不可避免构形都是可约的
雷  明
（二○二三年十一月十六日）

1，从图论中知道，任何平面图中都含有顶点度d≤5的不可避免顶点，所以在对其进行着色时，总可以把最后一个要着色的待着色顶点放在这样的不可避免顶点之上。把这样的还有一个顶点未进行4—着色的图就叫做平面图的不可避免构形。这就把待着色顶点的度由可以是有无穷多个的问题，转化成了只是有穷的六种不可避免构形的问题了。
2，只要解决了这有限的六种不可避免构形的可的性问题，四色问题也就解决了。因为对于任何一个平面图的着色来说，总可以把最后一个要着色的待着色顶点放在度是d≤5的顶点之上，对于度是d≥6的待着色顶点，可以不再去进行研穷了。这就为人用手工证明四色猜测创造了条件。
3，不可避免构形中围栏顶点占用颜色数小于等于3的构形，待着色顶点可以直接着色，是可约的终局构形，该图着色结束。否则，围栏顶点占用颜色数等于4的构形，是困局构形，只有4—度和5—度两种构形。
4，困局构形中能用坎泊链法直接从围栏顶点中空出某一种颜色给待着色顶点的构形是K—构形，坎泊在1879年早已证明该类构形是可约的。否则，不能用坎泊链法从围栏顶点中空出任何一种颜色的构形是H—构形，只剩5—度构形这一种。这类构形是坎泊证明中遗漏了的一个整类，是赫渥特在1890年发现的。赫渥特的H—图用坎泊链法就不能从围栏顶点中空出任何一种颜色来。
5，H—构形只所以不能用坎泊链法从围栏顶点中空出任何一种颜色，主要原因是图中含有双环交叉链。有了双环交叉链，围栏中的三个单色肯定是不能空出的。而不能移去两个同色主要是因为有了双环交叉链，从任何一个同色顶点进行了对角链的交换后，都会新生成从另一个同色顶点到其对角顶点的连通链，不可能连续的移去两个同色。由此可知，要解决H—构形的可约性问题，必须破坏双环交叉链，即把其断开，使图转化成可约的K—构形。
6，要断开双环交叉链，有四个关链的顶点，只要其中一个顶点的颜色发生了改变，原来的双环交叉链就都会断开。这四个关键顶点是：两链的共同起始顶点A和交叉顶点A（两顶点同色但不相邻），以及两链的两个末端顶点C和D（两顶点不同色且相邻）。
①要改变两链的共同起始顶点A或交叉顶点A（只能改变一个）的颜色，应交换由构形峰点的颜色A与两个同色顶点的颜色B构成的A—B邻角链。为了防止两个A色的关键顶点同时改变颜色，还必须要有一条经过了另外两个C色和D色关键顶点的C—D环形链，且把要改变其中之一颜色的两个关键顶点A分隔在环形链的两侧。交换了C—D环形链任一侧的A—B链后，图中原有的双环交叉链A—C和A—D就断开了，转化成的新构形是一个只能从围栏顶点中空出三个单色之一的K—构形。
②若要同时改变两链末端顶点的颜色，应交换的是该两顶点的颜色构成的邻角链D。同样的，也是为了不使图中所有的C和D的颜色都发生改变，也就必须要有一条经过了一个或两个A色关键顶点的A—B环形链，把经过了两链末端顶点的C—D链与其他的C—D链分隔在环形链的两侧。交换了环形链任一侧的C—D链后的新构形，是一个没有实质上“十字”交叉，但又含有两条连通链A—C和A—D的K—构形，只能移去两个同色B。
③以上两种交换的构形中，都有经过了关键顶点的环形链，所以叫做有环形链的H—构形，交换的方法叫做断链交换法，交换的是围栏顶点的邻角链，这一点与坎泊链法是不同的，坎泊链法交换的都是对角链。但断链法只能断开双环交叉链，使构形转化成K—构形，而不能空出颜色，最后还得使用坎泊链法空出颜色来。所以坎泊链法也可叫做可空出颜色的交换法。
7，有含有环形链的H—构形，也就应有无环形链的H—构形。这类构形既不能空出三个单色，也不能连续的移去两个同色。既然是这样，我们就只好先移去一个同色，使构形转型（也就是使其围栏顶点的颜色发生变化）。可以证明在有限的转型次数内，无环形链的H—构形都是可以转化成可约的K—构形的。
①过对一部分无环形链的H—构形的转型实践，都可以在极小有限的转型次数内转化成可约的K—构形。但这是不是一个普遍的规律呢？还需要进行逻辑的证明。转型实践得到的原命题是无环形链的H—构形经有限次转型后，都可转化成可约的K—构形。其逆否命题是经无穷次转型也不能转化成可约的K—构形的H—构形一定是含有环形链的H—构形。这个逆否命题是真的（如1921年埃雷拉构造的E—图就是这样的H—构形。E—图中含有环形链，无穷次循环转型也不能转化成可约的K—构形）。根据逆否命题与原命题有同真同假的逻辑关系可知，原命题无环形链的H—构形在有限次转型内是可以转化成可约的K—构形也是真的。这就证明了无环形链的H—构形的转型次数是有限的。
②任何5一度构形在进行了20次转型交换（5个围栏顶点，4种颜色，5和4的最小公倍数是5×4＝20）后，各围栏顶点的颜色又会恢复到转型开始时的初始状态。这是转型的一个循环周期。当转型次数达到了40次的两个循环周期时，才可以判断出是否是发生了无穷周期循环的转形。转型结束了的，就是有限转型的构形，否则就是无穷周期循环转型的构形。而我们这里所研究的无环形链的H—构形，已经证明是有限转型的构形，不可能产生无穷次的循环转型。所以该类构形有限转型次数的上界值只能是40，即任何无环形链的H—构形，一定都可以在有限的40次转型之内，转化成可约的K—构形或有环形链的H—构形。这里应注意的是，只要一旦转化成了有环形链的H—构形，就要立即改用断链法，以提前结束转型。
8，现在，平面图的各种不可避免构形的可约性均已讨论完毕，且都是可约的。这就从着色实践的角度证明了四色猜测是正确的，四色问题得到了彻底的解决。

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

雷明85639720

，，，，，，，，