四色问题的彻底解决——四色猜测是正确的！

雷明85639720

四色问题的彻底解决——四色猜测是正确的！
雷  明
（二○二二年八月七日）

【摘  要】通过对平面图的不可避免构形进行科学的多级分类，即，在每一级分类中，按一定的条件只把构形均分为“非此即彼”的两类，以防遗漏。其中一类在本级分类中就可以得到解决（可约），另一类可以留给下一级分类再进行细分。待到某级分类时，所分出的两类构形在本级分类中都可以得到解决（可约）时，多级分类即告结束。这样，平面图的各种不可避免的构形在各种情况下就都是可约的了，四色问题也就得到了解决。四色猜测也就得到了证明是正确的。
【关键词】四色问题  四色猜测  平面图的构形  不可避免构形  构形的多级分类  构形的可约性  色链（链）  相反色链  颜色交换技术  染色困局  颜色冲突  关键顶点  环形链  断链交换  转型交换
1、前言：
四色问题，也叫四色猜测。是一个关于给行政区划地图中的区域染色的问题。说的是“给任何地图中的区域各染以不同的颜色，要求有共同边界的两个区域的颜色都不相同，最多四种颜色就够用了”。这就是1852年英国的绘图员法朗西斯在给英国地图染色的过程中提出来的地图四色猜测。至今已有整整170年的历史了，但仍无法得到证明是否正确。
地图中的区划的边界线一般都很细，加上地图中还有河流，山脉，公路，铁路，城市等自然地形地貌以及人为的建筑物等，信息量是非常之大的。再把文字标注进去后，这样，就很难看清各区划的边界线，也看不明白各区划间的相邻关系到底是个什么样子。所以就要给地图中的各区划染以不同颜色（较浅的），以便进行区别。但又要求不会影响到自然地形地貌和人为建筑物的显示以及所标注文字的清晰。
猜测本身中所说的地图是指理论上的地图，即不存在有“国中之国”区划和有“飞地”的区划的行政区划的地图，也不存在有多于三条边界线相交于一点的区划的地图等。这种地图就是平时大家所说的“正规地图”。而在实际的行政区划地图中，不但存在着以上的各种情况，而且区域中还有陆地区域与海洋区域之分。实际地图中的陆地区域中，的确又存在着有四个国家（行政区划）两两均相邻的情况，至少要用四种颜色才能区分开来。这就是说地球地图单对陆地区划来说，至少就要占用四种颜色。但我们总不能把海洋和某些与海洋不相邻的内陆的陆地区划都染成相同的颜色吧。如果是这样，怎么能区分出哪一个区域是海洋，哪些区域又是内陆的行政区划呢？所以说实际地图的用色数一定是要大于等于理论上的正规地图的用色数的。但也不能用得太多。太多了，各颜色之间的差别就小了，也起不到清晰区分的作用。月球上没有海洋，全是陆地，如果能证明四色猜测是正确的，那么无论在月球上怎么划分区域，“月图”最多四种颜色就一定够用了。
2、把地理学问题转化成数学问题：
从图论的角度上去看，正规地图就是一个各顶点都是3—度（连接着3条边界线）的3—正则的平面图。它的对偶图就是一个各个面都是三边形面的极大平面图。给正规地图中面上的染色，就相当于对极大平面图的顶点着色。如果证明了极大平面图的四色猜测是正确的，那么已经4—着色的极大平面图，经“去顶”或“减边”运算后，所得到的任意平面图（极大平面图也是平面图中的一种），其色数就只会减少而不会再增加。这也就说明了任意平面图的四色猜测是正确的。这样，也就把一个地理学中的问题转化成了一个数学问题了。
3、把无穷的问题转化成有穷的问题：
给平面图着色时，总得要遇到最后一个要着色的顶点。把这样的还剩下一个顶点未进行4—着色的图就叫做“构形”。未着色的顶点叫待着色顶点，把与待着色顶点相邻的顶点叫围栏顶点。由于在图论中已有这样的已经证明过了是正确的结论，即任何平面图中都一定存在着至少一个顶点的度是小于等于5的。也就是说，在任何平面图中，可以没有大于等于6—度的顶点，但不可能没有度是小于等于5的顶点。或者说所有顶点全都是大于等于6—度的平面图是不存在的。
由于在平面图中存在有这样的性质，所以在给任何平面图着色时，总可以把待着色顶点放在度是小于等于5的顶点之上。其余的无穷无尽的度是大于等于6的顶点，就可以不再让其充当待着色顶点了。也就可以不再去研究度是大于等于6 的构形的可约性了。而只研究度是小于等于5的六种构形（即度分别是0、1、2、3、4和5的构形）中的待着色顶点如何着色就可以了。这就又把一个从平面图的个数上去看是无穷的问题，从各个平面图的顶点数上去看，也可以是无穷的问题，以及从图中的各顶点的度数上去看，仍可以是无穷的问题，统统就都转化成了一个有穷的问题了。
若把度是大于等于6的构形看做是“可以避免”的构形，那么，就可以把度是小于等于5的构形就叫做“不可避免”的构形。不可避免的构形是在对任何平面图着色的过程中总可以遇到的。这样，就自然的把“构形”分成了两类。这里就可以认为是对构形的一级分类。
在极大平面图中，每一个顶点与其相邻的顶点所构成的分子图都是一个轮形图，而在非极大的任意平面图中，各个顶点与其相邻的顶点所构成的分子图，有可能是轮形图，也有可能是星形图，还有可能是半轮—半星图。但由于在构成轮形图时先要构成的是星形图，所以我们统一把平面图的不可避免构形叫做n—星构形。在这个n—星构形的围栏顶点以外，再把围栏顶点间的“链”的连通情况表示出来，就是一个一般的非具体图的、且是非极大图的n—星构形的表示方法。
所谓“色链”就是由某两种颜色交替着色的道路，简称叫“链”。
4、平面图不可避免构形的科学分类：
构形分类的原则：多级分类的原则。每级只分两类，非此即彼，以防遗漏，以避免坎泊在1879年漏掉了整个含有双环交叉链的一类H—构形的失误再次发生。两类中其中一类在该级分类中就可以得到解决（可约），另一类留下等下一级分类时再进行细分。
一级分类：上一个问题就可以认为是构形的一级分类，即把构形分成了可以避免的构形和不可避免的构形两类。
二级分类：按围栏顶点所占用的颜色数是否小于等于3，把不可避免的构形再分成可以直接着色的构形（围栏顶点占用颜色数小于等于3）和不可以直接着色的构形（围栏顶点占用颜色数等于4）两类。可以直接着色的构形，问题也就已经得到了解决，接下来下一级分类再对不可直接着色的构形进行细分。不可直接着色的构形有人也叫“染色困局”构形或“颜色冲突”构形。
三级分类：按是否可以通过坎泊在1879年所创造的可以空出颜色的颜色交换技术，能否可以直接从围栏顶点中空出某一种颜色来，再把不可直接着色的构形再分成坎泊的可约的K—构形和“看似不可约”的赫渥特的H—构形两类。可约的K—构形早在1879年由坎泊已经证明是可约（即可4—着色）的了，问题也就得到解决了。现在主要就是要解决“看似不可约”的H—构形的可约性问题了。
所谓的坎泊的颜色交换技术，就是在不可直接着色的构形的围栏顶点中，如果在某两个对角顶点间的对角色链是不连通时，可以从一个顶点开始交换该链中各个顶点的颜色，即可从围栏顶点中空出交换开始顶点所用的一种颜色来。这时围栏顶点就减少了一种颜色，把从围栏顶点中减下来的这种颜色给待着色顶点着上即可。
由于在只有4个围栏顶点的不可直接着色的4—星构形中，一定有一对对角顶点的颜色所构成的对角色链是不连通的（因为在这种构形中，由四种颜色所构成的两种对角色链正好是相反的色链，即两链中没有相同颜色的顶点，是相互不能穿过的两条色链），所以，不可直接着色的4—星构形一定是可约的。
二级分类中分出的不可直接着色的构形从广义上讲，也都是“看似不可约”的构形，因为其围栏顶点已占用完了四种颜色。在下一节中将会看到，在这种构形中，的确是有一些构形是可以通过坎泊的颜色交换技术，直接可以从围栏顶点中空出某一种颜色来给待着色顶点着上的，是属于可约的K—构形一类的构形。所以说不可直接着色的构形从广义上讲，也都是“看似不可约”的构形。
5、对不可避免的H—构形的分析：


在BAB型的5—星构形中，含有不含有A—C链和A—D链的双环交叉链，是构成H—构形的必要条件。没有该双环交叉链不能构成H—构形，但有了它却不一定都是H—构形。比如在四个“九点形”构形中，都有双环交叉的A—C链和A—D链（如图1—4中的加粗边），但只有一个是H—构形（如图2），而其他三个都是可以连续的移去两个同色B的可约的K—构形（如图1，图3和图4）。
B—C链和B—D链也是两条双环交叉链（如图5），在含有这两条链的构形中，虽然不能连续的移去两个同色B，但却又是可以移去A、C、D三色之一，所以含有这种双环交叉链的构形也就不是H—构形了。看来H—构形中是一定要含有A—C链和A—D链的双环交叉链的（如图2和图6）。也正是因为有了双环交叉的A—C链和A—D链，也才有从一个B开始交换了一条关于B的链后，虽然移去了一个同色B，但又新生成了从另一个B到其对角顶点的关于另一个B的连通链，因而不能连续的移去两个同色B。加上A、C、D三色又不能移去，所以，从狭义上讲，H—构形才是真正的“看似”“不能移去”“任何一种颜色”的“不可约”的构形了。

看来，要解决H—构形的可约性问题，断开双环交叉链是一个关键的问题。如何解决这一问题呢？现在分析如下：
在H—构形中都有大于等于四个的关键的顶点：即双环交叉链的一个共同起始顶点A和大于等于一个的交叉顶点A（因为有些构形中的双环交叉链是有多个交叉顶点的），另外，还有双环交叉链的两个末端顶点C和D，至少有四个关键顶点（如图6中的四个加大顶点）。这几个关键顶点只要有一个顶点的颜色改变了，双环交叉的A—C链和A—D链也就不存在了。而要改变这几个顶点的颜色，就必须交换A—B链或C—D链。有没有这样的链可以交换呢？完全可以肯定的回答：有。但该链能不能交换，或者说交换后能不能起到断开双环交叉链的作用，就得要看构形中，还有没有与要交换的链呈相反链的并且经过了围栏顶点或关键顶点的环形链。即，若要交换的是A—B链，则必须要有环形的C—D链；若要交换的是C—D 链，则必须要有环形的A—B链。
在H—构形中，由A、B、C、D四种颜色所能构成的A—B链、A—C链、A—D链、B—C链、B—D链和C—D链这六种色链中，A—C链和A—D链已不能交换，虽然B—C链和B—D链还都可以交换，但却只能交换一个，也不能连续的移去两个同色B，所以该两链也就等于不能交换了。现在就只剩下可交换的A—B链和C—D链了。正好，上面已经进行了分析，要断开双环交叉链所需要交换的链就是这样的两条链。
为了防止在进行断链交换时，构形中所有的A、B（或C、D）顶点都改变颜色，起不到断链的作用，还必须要有一条经过了围栏顶点或关键顶点的环形的相反链C—D（或A—B）链把A—B（或C—D）链分隔在环形链内、外，成为互不连通的两部分。即，若含有环形的C—D链时，双环交叉链的共同起始顶点A和至少一个交叉顶点A一定要分别处于C—D环形链的两侧；若含有环形的A—B链时，双环交叉链的两个末端顶点C和D所构成的C—D链和其他的C—D链也一定要分别处于A—B环形链的两侧。根据这一条件，把H—构形再可分成有经过了关键顶点的环形链的构形和无经过关键顶点的环形链的构形两类。
有些构形中虽然看似也含有环形的C—D链，并且也经过了围栏顶点或关键顶点，但却不能把其相反链A—B中的两个关健顶点A分隔在环形链C—D的内、外两侧（如图7）。即就是交换了C—D环形链内、外的任一条A—B链，构形中仍然是含有双环交叉链的（如图8和图9）。
图7这样的构形是不应属于有环形链C—D的H—构形的。但该构形应属于哪一类，还要再看构形中还有没有其他的经过了围栏顶点或关键顶点的环形链（如图10，图11和图12）才能确定。



这里，可以看成就是对不可避免构形的第四次分类，即对“狭义的”“看似不可约”的H—构形的分类。
6、有环形链的H—构形的可约方法：
图13到图16是四个有双环交叉链A—C和A—D且含有环形链A—B的构形，但只有图13是一个H—构形，其他的三个都是可以连续的移去两个同色B的可约的K—构形；图17到图20也是四个有双环交叉链A—C和A—D且含有环形链C—D的构形，也是只有图17是一个H—构形，其他的三个也都是可以连续的移去两个同色B的可约的K—构形。这与前面说的虽然都含有双环交叉链，但却不一定都是H—构形的结论是相同的。



可以看出，图13从双环交叉链的两个末端顶点C和D开始在A—B环形链内交换C—D链（在环形链A—B外交换另一支C—D 链也是可以的），可使双环交叉链断开，转化成的构形中，虽然仍是含有共同起始顶点的两条连通链的构形，但却不是有双环交叉链的H—构形（图请读者自已画），而是一个可约的K—构形；
同样的，图17从双环交叉链的共同起始顶点（峰点）A开始在C—D环形链内交换A—B链（在环形的C—D链外从双环交叉链的交叉顶点A开始交换另一支A—B链也是可以的），也可使双环交叉链断开，构形转化成无任何连通链的可约的K—构形（图也请读者自已画）。

然后各再按解决K—构形可约性的方法去解决K—构形的可约就可以了。
这里所使用的方法虽然仍是坎泊1879年所创造的颜色交换技术，但它却没有从围栏顶点中空出颜色，而是只把双环交叉链断开了，使构形转化成了可约的K—构形。为了相互区别，就把这里所用的交换方法叫做“断链交换法”，而把坎泊使用过的交换方法叫做“可空出颜色的交换法”。1890年赫渥特构造的H—图，是一个有环形链C—D的H—构形，而1921年埃雷拉构造的E—图，则是一个有环形链A—B的H—构型，我们这里所构造的图10等，也是一个有环形链A—B（或C—D）的H—构形，也都是可以用断链法进行解决的。
7、无环形链的H—构形的可约方法：
图21到图24是也四个有双环交叉链的但又不含有任何环形链的构形，也只有图21和图22两个是无环形链的H—构形，其他的图23和图24两个图也都是可以连续的移去两个同色B的可约的K—构形。这与上面的结论仍然是一致的。再一次说明了不能把只要是含有双环交叉链的构形都说成就是H—构形。


从图21和图22可以看出，把图21中的C—D链中的一个顶点C的颜色改成A（如图25中的加大顶点）时，把图22中的C—D链中的一个顶点D的颜色改成A（如图26中的加大顶点）时，两个构形就都转化成了有环形链A—B的H—构形；
另一方面把图21中的A—B链中的一个顶点A的颜色改成D（如图27中的加大顶点）时，把图22中的A—B链中的一个顶点A的颜色改成C（如图28中的加大顶点）时，两个构形也就都转化成了有环形链C—D的H—构形了。


这都说明了无环形链的H—构形是可以向有环形链的H—构形转化的。然后再按解决有环形链的H—构形的办法去解决即可。图21和图22这样的由无环形链的H—构形转化成有环形链的H—构形的过程也是可以逆向进行的。这说明不光是无环形链的H—构形可以转化成有环形链的H—构形，而且也说明有环形链的H—构形也是可以转化成无环形链的H—构形的。
现在要问，有没有无环形链的H—构形不可以转化成有环形链的构形呢？回答是：没有。用反证法进行证明：如果说存不能转化成有环形链的H—构形的无环形链的H—构形，就说明H—构形有三类，一类是有环形链的H—构形，二类是可以与有环形链的H—构形相互转化的无环形链的H—构形，三类是不能转化成有环形链的H—构形的无环形链的H—构形。但是我们这里所说的H—构形中的前提条件是，只有有环形链的H—构形和无环形链的H—两种构形，即只是“非此即彼”的两类构形。而这里证明的假设却有三类，与前提条件是矛盾的，应该否定假设。这就证明了无环形链的H—构形一定是可以转化成有环形链的H—构形的。也就是说根本就不存在不可以转化成有环形链的H—构形的无环形链的H—构形。
这样的反证法证明似乎好象理由有点不大充分，似乎还不能说明无环形链的H—构形就一定不存在不可转化成有环形链的H—构形的构形的可能，难以使人所接受。为了弥补这一问题，在下面第8个问题中，还有用连续转型的方法解决无环形链的H—构形的可约性的办法。

以上所看到的是有环形链的H—构形与无环形链的H—构形的相互转化，实际上有环形链的两种H—构形也是可以相互转化的。把图13中的有环形链A—B的H—构形中的两个顶点A的颜色分别改成D和C（如图29中的两个加大顶点），有环形链A—B的H—构形就转化成了有环形链C—D的H—构形了（如图30）；这样的过程也是可以逆向进行的，一个有环形链C—D的H—构形（如图17和图30），也是可以转化成有环形链A—B的H—构形的（如图29和图13）。
8、无环形链的H—构形经有限次同方向连续转型也是可约的：
无环形链的H—构形中由于既没有环形的A—B链，也没有环形的C—D链，所以C—D链和A—B链也就都不能交换了。四种颜色所能构成的六种链中，已有四条不能交换了。剩下的两条关于两个同色B的链，又不能连续的进行交换，也不能移去两个同色B。怎么办？若只交换一条关于两个同色B的链时，虽不能移去两个同色B，但可以使构形转型，这也就出现了转机。然后再看转型后的构形是否可约。现在，唯一的办法也只能是先交换一条关于两个同色B的链，使构形转型了。

所谓转型 ，就是从一个B色顶点开始，交换一条关于两个同色B的链，使构形峰点的颜色和位置都发生变化，生成另一类型的新的5—星构形。如图31是对图21从左B开始进行交换的逆时针方向转型，把BAB形的构形转化成了DCD型的构形；图32是对图21从右B开始进行交换的顺时针方向转型，把BAB型的构形转化成了CDC型的构形。图31再连续逆时针方向转型一次后，就是一个可以连续的移去两个同色的可约的K—构形，图32目前已经是一个含有经过了两个围栏顶点（也是关键顶点）的环形链A—B的H—构形了，可以再按有环形链的H—构形的处理方法进行解决了。
现在的问题是，这个“有限次”转型交换的结论是如何得来的？并且要解决“有限次”的上界值是多少的问题？要知道，没有上界值的“有限”仍相当于是“无限”的。如果不解决这个问题，无环形链的H—构形的可约性问题就还等于没有解决。
上面我们说了，埃雷拉E—图（如图33和图34。图33的待着色顶点是隐形画法，图34的待着色顶点是显形画法）是可以用断链法进行解决的有环形链A—B的H—构形。但是若对E—图构形使用转型法时，却是一个无穷周期循环转型的构形，永不得解。所谓一个循环，就是指各顶点的颜色均回到了转型开始时的原始状态。

E—图是一个特殊一点的H—构形，除了含有双环交叉的A—C链和A—D链、且不能连续的移去两个同色B外，还含有经过了一个关键顶点A（双环交叉链的共同起点）的环形的A—B链和含有不经过关键顶点的环形的C—D链。这两条环形链并没有相交叉的相互穿过，而是象两个同心园一样的结构的两条环形链，是没有交叉顶点的（如图33和图34中的加粗边）。E—图又是一个左右对称的轴对称图形。有了这些特殊的特征，当然也就与一般的H—构形有不同的性质。
前面的图10也是一个与E—图特征相似的构形，都是在经过了关键顶点A的环形链A—B内（或外）嵌套着一个同心园式的C—D环形链（图10中的环形的C—D链未进行加粗）。两个图都是一个左右对称的轴对称图形。所不同的是，E—图的C—D环形链虽未经过关键顶点，但却把另外的两个关键顶点A分隔在了C—D环的两侧；而图10中的C—D环形链虽然经过了关键顶点，但却没有把另外的两个关键顶点A分隔在C—D环的两侧。正因为如此，所以这两个图只能是属于有环形链A—B的H—构形，也只能用交换C—D链的断链法解决；而不是属于有环形链C—D的H—构形，也不能用交换A—B链的断链法进行解决。这是两个比较特殊一点的H—构形。
根据E—图是一个无穷周期循环转型也永不得解决问题的结论，利用“逆否命题与其原命题同真同假”的逻辑关系，可判断得出，有限次转型可以解决问题的H—构形也一定不是E—图构形的结论。也就是说，不单仅仅是无环形链的H—构形的转型次数一定是有限的，而且是任何只要不是E—图构形的H—构形，其转型的次数一定都是有限的，也包括有环形链的H—构形在内。但“有限的”上界值是多少呢？现在再来进行分析：
任何5—星构形（包括E—图在内）转型时，即就是转型次数达到了5—星构形的“固有周期”（20次转型）时，由于第二个周期（40次转型）还没有来临，所以还是不能判断其是否就是无穷周期循环的构形。只有等到第二个循环周期即第40次转型来到时，才能确定。而我们这里所研究的无环形链的H—构形，已经知道其是有限次转形的，第二个循环周期一定是不可能来到的。所以，连续转型就必须在第二个循环周期即40次转型到来之前结束。这样，有限次的上界值就可以确定为40次转型。即任何无环形链的H—构形在连续转型时的转型次数一定在不超过40次转型时，就可以解决问题。在转型的过程中，随时也都有转化成有环形链的H—构形的可能。也都是可以随时改变成用断链法进行解决的，可以提前结束转型。
的确，笔者与另一位未曾谋面的山西省的业余四色爱好者同行朋友张彧典先生都曾构造出过转型次数高达20次以上的H—构形，但转型次数的确又没有超过40次，没有到达第二个转型周期的来临。
无环形链的H—构形的解决方法，除了以上的直接转化成有环形链的H—构形和转型法外，还可以利用有局部环形链的局部断链法（即只断开一条连通链的方法）解决问题。总之，无环形链的H—构形的解决办法不但是多种多样的，而且还是可以相互转化的，非常的灵活，用起来也很方便。
这就证明了无任何环形链的H—构形一定是会在有限的40次转型之内解决问题的。即无环形链的H—构形也是可约的。
9、四色猜测被彻底证明是确的：
现在，平面图不可避免的构形在各种情况下都是可约的了，四色猜测也就证明是正确的了。
10、一点说明：
    有人可能会问，你证明时用的是可以代表任意平面图构形的非极大图的构形，证明了这种构形的四色猜测是正确的，能够说明极大平面图的四色猜测也都是正确的吗？能。为什么，因为极大平面图也是一种平面图呀！极大平面图也是任意平面图中的一种存在形式呀！所以，反过来说，证明了任意平面图的四色猜测是正确的，同样也就证明了极大平面图的四色猜测也是正确的。当然地图的四色猜测也就是正确的了。

雷  明
二○二二年八月七日于长安

注：此文的初稿《四色问题的彻底解决》已于二○二二年八月十四日在《数学中国网》的《哥猜等难题与猜想》栏目中发表过，网址是：
http://www.mathchina.com/bbs/for ... =2053286&extra=

雷明85639720

，，，，，，，

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，