解决四色问题的关键是把构形围栏顶点占用的颜色数由四种减少到三种

雷明85639720

解决四色问题的关键是把构形围栏顶点占用的颜色数由四种减少到三种
雷  明
（二○二○年九月十四日）

1、地图是一个无割边的3—正则平面图，给地图的面上的染色就相当于对其对偶图——极大平面图——的顶点着色。这就把一个地理问题转化成了数学问题。
2、如果极大图是可4—着色的，经去顶或减边后所得到的任意平面图的色数只会减少而不会再增加，所以地图四色问题也就是一个任意平面图的四色问题。
3、对连通平面图着色时，总是一个一个顶点的着，也总会有最后一个顶点要着色的问题。把只有一个顶点未着色的图叫做“构形”。未着色顶点叫待着色顶点，把与待着色顶点相邻的顶点叫围栏顶点。可以看出，构形中除了待着色顶点未着色外，其他所有顶点都是已着了色，并且是符合四色要求的色图。
4、由于任何平面图中一定存在着一个度小于等于5的顶点，所以在着色时，也总可以把最后一个待着色顶点放在度是小于等于5的顶点之上。所以在研究平面图的四色问题时，只要研究待着色顶点的度是小于等5的构形就可以了。这就又把一个研究对象可以是无穷多构形的着色的无穷问题，转化成了只研究顶点度是不大于5的五种构形的着色的有限问题了。
5、顶点度是小于等于3的构形，由于围栏顶点最大只可占用三种颜色，所以待着色顶点一定是至少还有一种颜色可着的，不须要再专门的研究了。
6、而顶点度是等于4或5的构形，围栏顶点都有占用完四种颜色的可能。这种情况的构形中的待着色顶点该如何着色？是研究四色问题时的主要的关键问题。这种情况就是平时说所的“颜色冲突”现象。
7、解决颜色冲突现象主要是要把构形围栏顶点所占用的颜色数由四种减少到三种，把减下来的一种颜色给待着色顶点着上，颜色冲突的问题就解决了。只要把所有可能发生的颜色冲突现象都解决了，四色问题也就解决了。
8、由两种颜色交替着色的一个序列叫做“色链”，简称“链”。若两种链的颜色均不相同时，这两种链就叫做“相反链”，如把由A和B构形的A—B链和由C和D构成的C—D链就叫一对相反链。
9、若有一条链自已构成了环，或与待着色顶点共同构成了环时，则其相反链一定是被构成环的链分隔在环内、环外两部分，互不连通。交换环链内、外的任一部分相反链，都是不会影响到另一部分相反链中各顶点的颜色的。
10、利用9中的原理，1879年坎泊已经证明了顶点度等于4的构形是可约的，即这种构形是能够把围栏顶点的颜色由四种减少到三种的，颜色冲突的问题是可以解决的。“可约”也就是“可4—着色”的意思。
11、待着色顶点是4度的构形，若围栏顶点的颜色依次是A、B、C、D，如果对角顶点A和B构成的色链A—B从A到B是连通的，则其与待着色顶点V就构成了一个环。从另外两个围栏顶点C和D的任何一个顶点开始交换C—D链，则C（或D）色顶点就变成了D（或C）色顶点，空出了C（或D）色，给待着色顶点V着上。这个待着色顶点是4度的构形的颜色冲突就解决了，这个构形也就是可约的了。当4—度构形的一对相反链各都不连通时，则从任一个围栏顶点开始交换与其对角顶点的颜色构成的对角链时，都一定可以空出一种颜色给待着色顶点V着上，构形也是可约的。
12、待着色顶点是5度的构形，若围栏顶点的颜色依次是1B、2A、3B、4D、5C，且没有任何连通链时，可以从2A、5C、4D三个围栏顶点进行对角链的交换，空出A、C、D三色之一给待着色顶点。若2A与5C（或4D）连通时，可以从2A（或4D）交换A—D链，空出A（或D）给V；若2A与4D（或5C）连通时，可以从2A（或5C）交换A—C链，空出A（或C）给V；若2A与5C和2A与4D分别连通（但不交叉）时，可从两个B色顶点分别交换B—C链与B—D链，连续的移去两个同色B，把B给V着上。构形也是可约的。
13、但坎泊在证明顶点度是5的构形时，却遗漏了一种含有“双环交叉链”的构形，就使得他的证明并不彻底。若使12中所说的A—C和A—D两条连通链在中途又有相交叉的顶点A，并且各链已均与V构成了一个环，所以就叫“双环交叉链”。这种构形是在1890年由赫渥特发现的，并因此给坎泊的证明进行了否定。现在证明四色问题，主要就是解决具有“双环交叉链”的构形是否可约的问题。
14、对与具有双环交叉链的构形，肯定是不能直接空出A、C、D三种颜色之一的，因为A—C链和A—D链均是连通的。但该构形只要从一个B色顶点交换了与其对角顶点的颜色构成的色链后，不能新生成从另一个B色顶点到其对角顶点的连通链时，就可以连续的移去两个同色B。否则，也就不能直接空出B来了。
15、对于14中的所说的后一种构形来说，虽然不能直接空出任何颜色，但是可以把构形转化成不含双环交叉链的可约构形。从该构形可以看出，A—C和A—D两链的共同起始顶点2A、相交顶点A和两链的末端顶点5C和4D四个顶点都是关键的顶点。只要这几个顶点的颜色改变了，双环交叉链也就不存在了。这样的交换就叫做“断链交换”。
16、为了改变5度构形中这四个关键顶点的颜色，构形中必须含有经过围栏顶点的环形链，以避免交换某链时，使图中所有着有所交换的链中的两种颜色的顶点全部换色一遍，使得交换无效。当有A—B环形链时，交换A—B环内、外的任一条C—D链；当有C—D环形链时，交换C—D环内、外的任一条A—B链；都可以使构形变成无双环交叉链的可约构形。颜色冲突的问题也就解决了。
17、对于14中的构形来说，若不含有经过围栏顶点的环形链时，虽不能连续的移去两个同色B,但可以先移去一个B，使构形“转型”。所谓转型，就是指构形峰点的位置和颜色都发生了改变。例如一个围栏顶点着色次序为1B、2A、3B、4D、5C的123—BAB型的构形，从1B交换了B—D链后，构形就变成了451—DCD型的构形，峰点由2A变成了5C。这就是“转型交换”。
18、对于17中的只能进行转型交换的构形来说，按同一转型方向需要多少次连续的转型，才能解决问题呢？这也是一个必须解决的问题。否则，四色猜测还是不能得到彻底证明的。
19、对于度是5的所有颜色冲突的构形来说，都是可以进行转型交换的。其中有一类构形（如埃雷拉（Errera）图等）是以每20次转型为一个周期的无穷循环转型的构形，转型永远也是不会结束的。
20、埃雷拉图是Errera在1921年给出的，埃雷拉图类构形中都含有经过围栏顶点的环形的A—B链，可以用断链交换法解决问题。1935年美国人Kittell用一种叫“正切链”的术语来指由相关联顶点所决定的色链，给埃雷拉图的待着色顶点进行了4—着色；我国的敢峰在1992年，张彧典和雷明在2010年，也都用“断链法”分别对埃雷拉图进行了4—着色。Kittell的所谓“正切链”法，实际上也就是“断链法”，都是从4D或5C开始交换C—D链，使得A—C链和A—D链都断开的方法。交换后，虽然图中仍还有连通的A—C链和A—D链，但这两链却不是原来的A—C链和A—D链，且两链也是不相交的，是一个可空出两个同色B的可约构形，该图颜色冲突的问题得到了解决。
21、而17中所说的不含有经过围栏顶点的环形链的构形，转型的次数会不会也出现象埃雷拉图一样的无穷循环呢？不会的。因为这种构形本身就是无环形链的构形，不可能含有象埃雷拉图那样的经过了围栏顶点的A—B环形链，根本就不含有产生无穷循环转型的条件。所以，这类构形一定会在20次（包括第20次）转型之前，就会转化成可以连续的移去两个同色的可约构形的。这也就解决了无环形链的构形的颜色冲突的问题。我们对多种无环形链的构形的转型着色实践也已经证明了这一结论是正确的。
22、现在，平面图的5种不可避免的构形在各种请况下的颜色冲突现象都已经解决，并且再也没有别的颜色冲突现象了。这就证明了平面图的四色猜测是正确的，也证明了地图的四色猜测是正确的。

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

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

雷明85639720

，，，，，，

雷明85639720

，，，，，，

雷明85639720

，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，