埃雷拉E—图的可4—着色

雷明85639720

埃雷拉E—图的可4—着色
雷  明
（二○二二年四月十九日）

图1 是埃雷拉在1921年构造的一个图（构形），是一个与待着色顶点相邻的顶点已占用完了四种颜色的、发生了颜色冲突的H—构形。现分析和着色如下：

1、与待着色顶点V相邻的顶点叫围栏顶点（如图2中加粗边所连的顶点。

2、在围栏顶点间有两条相交叉的A—C和A—D连通链，叫“双环交叉链”（如图3中的加粗边，其中一条用虚粗线表示）。
3、由于A—C和A—D均连通，所以从围栏顶点中是空不出颜A、C、D三色之一的。而在交换了B—C（或B—D）链，移去了任一个B后，又会新生成从另一个B到其对角顶点的连通链B—D（或B—C），不可能连续的移去两个同色B（如图4 和图5。其中粗虚线边是交换过的链，粗实线边是新生成的连通链）。

4、由A、B、C、D四种颜色可能构成的A—B、A—C、A—D、B—C、B—D和C—D六种链中，已有A—C、A—D、B—C和B—D四种链不能交换了，还有A—B和C—D两种是可以交换的，就看如何的利用这两条链了。
5、由于含有双环交叉链是构成H—构形的必要条件，即没有它不能构成H—构形，但有了它却不一定都是H—构形。现在只有想办法断开双环交叉链，使构形变成为可约的K—构形。
6、要断开双环交叉链，两链的共同起始顶点A和交叉顶点A，以及两链的两个末端顶点C和D这四个顶点是关键的顶点，只要其中一个顶点的颜色发生了变化，图中就不存在双环交叉链了。
7、图中已有一条环形的A—B链（如图6中的加粗边），虽然交换了环形链起不到什么大的作用，但该环形链A—B却把C—D 链分隔成了互不连通的两部分（如图7）。交换了A—B环形链内、外的任一部分C—D 链，原来两条连通的双环交叉链就均已断开，而新生成了不再交叉的两条连通链A—C和A—D（如图8和图10）。


8、图8和图10中虽仍有连通的A—C链和A—D链，但两链却不相交叉，都是可以连续的移去两个同色B的可约的K—构形。图9是从图8中移去了两个同色B而给V着色的结果，图11是从图10中移去了两个同色B给而给V着色的结果。
9、这里的E—图的画法只是米勒和张彧典的一种画法（即是埃雷拉地图画法的对偶图。我在他们的待着色顶点的隐形画法基础上增加了待着色顶点V），若改用雷明的画法，张彧典的另一种画法，敢峰的画法，以及其他人的画法时，也是同样的处理办法。

10、有些人不研究构形的可约性，不明白为什么要用有限的构形来替代无穷的图来进行研究四色问题，他就不可能对E—图进行可4—着色。可是他们也深信E—图是可以4—着色的，所以就只好对E—图的裸图（未着色的图）从头再进行着色，这就太麻烦了。以后再遇到这样的问题怎么办呢？把已着过颜色的部分重新推倒，重新着色吗？顶点少了还可以，顶点太多了如何办呢？所以说不研究构形的可约性还是不行的，不总结经验也是不行的。把所有有限的不可避免的颜色冲突构形都可以解决了，四色猜测也就被证明是正确的了。

11、虽然图1中也有环形的C—D链（如图12），也把A—B链分隔成了互不连通的两部分（如图13），但却不能在C—D环的内、外交换A—B链，因为C—D环形链并没有经过关键顶点C和D，而A—B环形键却是经过了关键顶点A的。如果要交换，虽然原来的双环交叉链也断开了，但却新生成了新的双环交叉链（如图14和图15），图仍是H—构形。

12、不仅如此，即就是含有经过了关键顶点C和D的C—D环形链，但又没有把两个关键顶点A分隔在C—D环的内、外两侧，也是不可交换C—D环内、外的A—B链的。即就是交换了，仍是含有新的双环交叉链的H—构形（如图16）。读者可以自已去检验，我这里也就不再画图了。

13、看来，环形链A—B和C—D不但要经过了关键顶点，而且还必须能够把各自的相反链（A—B和C—D是互为相反链的）分隔成环内、环外呈互不连通的两部分。图1中E—图中的A—B环形链是能够满足这个要求的，而E—图中的C—D链和图16中的C—D链都是不能满足这一要求的。

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

雷明85639720

，，，，，，，，