四色问题是可以手工解决的（修改稿）

雷明85639720

四色问题是可以手工解决的（修改稿）
雷  明
（二〇二二年五月三十日）

四色问题也叫四色猜测。说的是对地图中各区域进行染色，使任何两个相邻的区域都不用同一颜色的情况下，任何一张地图，最多四种颜色就够用了。这是1852年英国的绘图员法郎西斯在给地图染色时提出的一个猜测，即地图四色猜测。至今一个半多世纪已经过去了，仍没有从理论上证明其是否正确。
1、把地理学中的问题转化成数学问题
给地图的染色原本是一个地理学中的问题，染色的目的是为了使地图中弯曲的边界线能看得更清楚。因为地图本身就是一个3—正则的平面图，所以给地图中区域的染色就相当于对其对偶图——极大平面图——的顶点着色。因此，只要能证明任何顶点数的极大平面图的四色猜测是正确的，地图的四色猜测也就是正确的。只要极大平面图的四色猜测是正确的，由极大平面图经去顶或减边，或经去顶和减边同时运算所得到的非极大的任意平面图的色数只会减少而不会再增大，所以，任意平面图的四色猜测也就是正确的了。这就把一个地理学中的问题转化成了一个数学问题。研究起来也比较方便。
2、平面图着色中的“构形”
对平面图着色，总是一个顶点一个顶点的着，也总存在着最后一个要着色的顶点。与该顶点相邻的顶点所占用的颜色数小于4时，该顶点一定是可以着上图中已用过的四种颜色之一的，该图的可4一着色就成功了。若与该顶点所相邻的顶点所占用的颜色数等于4时，如何给该顶点也能着上图中已用过的四种颜色之一，就是四色问题研究的主要任务。这种情况有人叫“染色困局”，也有人叫“颜色冲突”现象的。象这样的只有一个顶点未着色，其他顶点都进行了可4—着色的极大平面图，坎泊在研究四色问题时，就叫做“构形”，现在大家也都是这样叫的。构形中未着色的顶点叫“待着色顶点”，与待着色顶点相邻的顶点叫“围栏顶点”。在画构形时，一般情况下只画待着色顶点和围栏顶点，其他已经4—着色的顶点是不画出的。各种情况下的构形中的待着色顶点都能着上图中已用过的四种颜色之一时，四色问题也就解决了。这就可以用只研究构形的“可约”性（坎泊语）来代替对全图中所有顶点的全部着色。
3、把无穷问题转化成有穷问题
极大平面图有无穷多个，每个极大图中的顶点也可以是无穷多的，图中每个顶点的度也可以是无穷多的，这就决定了极大平面图着色时所研究的对象——构形——也一定是无穷多的。既是无穷多的，当然也就是永远也研究不完的。但图论中却可以证明任何平面图中都至少含有一个顶点的度是小于等于5的。也就是说，各顶点的度全部是大于等于6的平面图是不存在的。这就为着色时一定能把最后的待着色顶点放在度是小于等于5的顶点之上创造了条件。度是小于等于5的顶点成了平面图中的不可避免顶点，待着色顶点的度是小于等于5的构形也就成了平面图的不可避免构形。这就把一个无穷的问题转化成了有穷的问题。各种情况下的有限个不可避免构形都是可约的了，四色问题也就解决了。
4、构形的一级分类（按不可避免性分）
平面图的构形按其不可避免性可分为可以避免的构形和不可避免的构形两大类，非此即彼，不会产生遗漏。待着色顶点的度是大于等于6时，是可以避免的构形；待着色顶点的度是小于等于5时，是不可避免的构形。可避免构形的是否可约，可以不去研究它，因为着色时可以不把最后的待着色顶点放在度是大于等于6的顶点之上的，也不会产生6度上的待着色顶点的构形。只要集中力量研究有限的几种不可避免构形的可约性就可以了。
5、构形的二级分类（按待着色顶点是否可以直接着色分）
平面图的不可避免构形中，围栏顶点数小于4或围栏顶点所占用的颜色数小于4的构形，其待着色顶点是可以直接着色的，就是待着色顶点可以直接着色的构形。而平面图的不可避免构形中，围栏顶点数大于等于4（只有4和5两种）的，并且围栏顶点所占用的颜色数等于4的构形，则是待着色顶点不可直接着色的构形。需要使用坎泊的颜色交换技术，才能从围栏顶点所占用的颜色中空出某一种颜色来，给待着色顶点着上，使待着色顶点着上图中已使用过的四种颜色之一。
6、坎泊的颜色交换技术
颜色交换技术是坎泊在1879年证明地图四色猜测时所创造的一种着色（或证明）的方法，有人也叫坎泊链法。用两种颜色交替着色的道路就是一条色链，简称为“链”。交换链中各顶点的颜色，可以达到改变链中某一个顶点颜色的目的。在构形中，若两个对角围栏顶点的颜色所构成的链对于该两个顶点是不连通的时，则可以从两对角顶点的任一个围栏顶点开始，交换这一色链。交换后，交换起点的围栏顶点的颜色就会发生变化，变成其对角顶点的颜色，围栏顶点所占用的颜色就会减少一种。而两对角围栏顶点的链若是连通链时，却是不能交换的，是不能从围栏顶点中空出颜色的。但是，只要有这种连通链情况存在时，其相反链一定是不连通的。因为两条相反链中的颜色均是不同的，是不可以相互穿过的。交换了另一条不连通的相反链也是可以空出颜色来的。
7、构形的三级分类（按可否从围栏顶点中空出颜色分）
对于不可直接对待着色顶点着色的构形来说，通过坎泊的颜色交换技术，可以分为可以直接从围栏顶点中空出颜色的构形和不可以直接从围栏顶点中空出颜色的构形。1879年坎泊已证明了4—轮颜色冲突构形和大部分的5—轮颜色冲突构形都是可约的（即大伙所说的K—构形），而把含有双环交叉链且不能空出任何颜色的5—轮颜色冲突构形遗漏了。坎泊所遗漏的这种构形就是不能从围栏顶点中空出颜色的构形。它是在1890年由赫渥特发现的，所以大伙都叫它H—构形。现在研究四色问题主要就是要解决H—构形的可约性问题。H—构形也有几种表现形式（见下一级分类）。
8、H一构形的关键顶点
在H—构形中，一定存在着双环交叉链A—C和A—D（如图1中的加粗链。这并不是赫特图的原图，而是赫渥特图原图的简化图），两链既然都是连通的，并且又与待着色顶点一起构成“环”了，那肯定是不能通过坎泊的颜色交换技术空出A，C，D三色之一的。有了双环交叉链，才能构成H—构形，也才不可能连续的移去两个同色B。因为移去了一个围栏顶点的B后，就会新生成从另一个B到其对角围栏顶点的连通链，使得不可能连续的移去两个同色B。这就是H—构形不能从围栏顶点中直接空出任何一种颜色的原因。

顺便再多说一点，在5—轮构形中，不但可以存在双环交叉的A—C链和A—D链，而且也可以存双环交叉的B—C链和B—D链。但在这种情况下的A—C链和A—D链都是绝对不连通的，是可以交换的，总是可以从围栏顶点中空出A、C、D三色之一的，是属于K—构形。
要从H—构形的围栏顶点中空出某一种颜色，就必须破环双环交叉链，即让双环交叉链断开，使构形转化成可约的K一构形。从图1中可以看出，要使双环交叉链断开，构形围栏顶点的峰点A，双环交叉链的交叉顶点A，以及双环交叉链的两个末端顶点C和D，是四个关键的顶点。这四个顶点中，只要有一个顶点的颜色发生了改变，图中就不再存在双环交叉链了，构形就转化成了可约的K一构形了。
9、如何断开双环交叉链
由A，B，C，D四种颜色可能构成的六种色链，在H—构形中已有A—C，A—D，B—C，B—D四种链是不能交换的，现在可以交换的只能是A—B链和C—D链了。关键顶点颜色的改变，双环交叉链能否断开，构形能否从H—构形成转化成K—构形，也正好就是要靠交换这两种链了。
①要改变双环交叉链的两个末端顶点的颜色，就得要从这两个关键顶点开始交换C—D链，但又要使双环交叉链上的所有着C和D的顶点不全部改变颜色，图中就必须要有一条环形的且至少经过了一个A色关键顶点的A—B链（如图2中的加粗圈），把关键顶点C和D与其他的C色和D色顶点分隔在A—B环的两侧。

②要改变构形峰点A或双环交叉链交叉顶点A的颜色，就得分别从这两个顶点开始交换A—B链，但又要使另一个A色顶点不变色，图中也必须要有一条环形的且经过了关键顶点C和D的C—D链（如图3中的加粗圈），把两个A色关键顶点分隔在环的两侧。图3和图1是同一个类型的H—构形，都是有环形链C—D的H—构形。
以上两种交换的结果都使得双环交叉链断开了，构形转化成了可约的K—构形，所以就叫“断链交换”。
③有环形链的构形，可以通过断链交换使构形转化成可约的K—构形，而没有环形链的构形（如图4），A—B链和C—D链各都只是一条直链，且均不成环状。又该怎么办呢？既然这种构形，不能连续的移去两个同色B，那么，可不可以先移去一个B，使构形转型，再看转型后的构形是否可转化成可约的K—构形呢？
10、构形的四级分类（按有没有环形链分）
不可通过坎泊的颜色交换技术直接从围栏顶点中空出任何一种颜色的H—构形的分类，实际上在上节《9，如何断开双环交叉链》一节中就已经进行了。分为有环形链的构形（如图1，图2和图3）和无环形链的构形（如图4）两类。有环形链的构形又可再分为有A—B环形链的构形（如图2）和有C—D环形链的构形（如图1和图3）两个子类。这两个子类都可用断链法使构形转化成可约的K—构形。有A—B环形链的交换C—D链，有C—D环形链的交换A—B链（读者可自行交换一下）。无环形链的构形不可进行断链交换，只能进行转型。

11、使无环形链的H一构形转化成可约的K一构形的方法
从图4中的围栏顶点的右B点开始进行顺时针方向转型，虽然仍是一个含有D—A链和D—B链的双环交叉链的CDC型的H—构形，但图中却含有环形的A—B链，可以用断链法进行解决（如图5），使H—构形转化成可约的K—构形。
从图4中围栏顶点的左B点开始进行逆时针方向的转型，一次转型后是一个DCD型H—构形（如图6）。
二次转型后是一个只有一条B—C连通链的ABA型的可约的K—构形（如图7）。但在平面图范围内还，图7还可以继续构造连通的B—D链（如图8），又是一个H—构形。
对图8进行第三次转型后，是一个只有一条D—B连通链的CDC型的可约的K—构型（如图9）。在平面图范围内也还可以继续构造连通的D—A链（如图l0），仍是H—构形。



对图10进行第四次转型，也是只有一条A—D连通链的可约的K—构形（如图11）。在平面图范围内也可以构造另一条连通链A—C链（如图12）。图12就转化成了一个可以连续的移去两个同色B的可约的K—构形。再经过两次交换后，就可空出B给待着色顶点着上（如图13和图14—1）。当然也可以给待着色顶点着上C（如图14—2）。
图4的无环形链的构形最多只经过了四次逆时针转型就转化成了可约的K—构形（其中转化中途已多次都是K—构形，并多次人为构造了双环交叉链的）。整个逆时针转型的过程中，也还没有遇到转化成有环形链的可用断链法的情况。


如果对图4中的列环形链的构形按顺时针转型，也进行连续的转型（转化成可约的K—构形后，也仍人为的构造双环交叉链），也是在最多不超过四次转型，就可转化成可约的K—构形（如图15到图20）。




无环形链的H—构形转化成可约的K—构形的其他方法：

从图4中可以看出，无环形链的H—构形，至少有两个顶点（如图21中的加大顶点）是由无环形链向有环形链转化的关键顶点。把加大的C色顶点改成A色时，图4就转化成了与图2相同的有环形链A—B的H—构形（如图22），把加大的A色顶点改成D色时，图4就转化成了与图3相同的有环形链C—D的构形了（如图23）。二者都可以用断链法使H—构形转化成可约的K—构形。

另外，在双环交叉的A—C或A—D链中，若存在三色以下的偶轮（如图24右上方的加粗分子图），把该轮的轴心顶点A的颜色改成B或D时，也都可以使H—构形转化成只有一条连通链的可约的K—构形。
12、无环形链的H—构形有限次转型的上界值
到上节《11，使无环形链的H—构形转化成可约的K—构形的方法》一节，可以说四色猜测就已经证明是正确的了，因为我们已经证明了各类不可避免的构形在各种情况下，都是可约的了。但对于图4的无环形链的H—构形在施行两个方向的转型时，虽然都在四次转型之内都有转化成可约的K—构形的情况，但在逆时针转型时，却没有转化成有环形链的构形，而是在有限的四次连续转型后，直接转化成了可以连续的移去两个同色的可约的K—构形。是不是还有需要比四次更多次连续转型的构形呢？这个有限次转型的上界值是多少呢？还不能确定。因为无上界值的有限次也可以认为是无限次。这样，不就仍然等于四色猜测还没有被证明是否是正确的吗？本节就来专门的谈论这个向题。
图25是1921年埃雷拉所构造的埃雷拉E—图（该图原图是不画出待着色顶点的画法，我给其增加了待着色顶点，所以就成了待着色顶点画在图最外边的画法，与本文前面各图的待着色顶点画在图内部的画法有所不同）。

该图是一个有双环交叉链的，并且有环形链A—B的BAB型的H—构形，是可以通过断链法解决问题的，是一个可约的构形。但该图在进行转型时，却是一个以20次转型为周期的无穷周期循环转型的构形，永远也是解决不了问题的。与E—图不同的图也是有无穷多的，不可能通过具体转型的过程去证明每一个非E—图都是有限次转型的，也不可能证明其中是否还也有无穷周期循环转型的构形。这就只能借用“原命题的逆否命题与其原命题同真同假”的逻辑推理来进行判断。
在这里原命题是“E一图是无穷周期循环转型的构形”，且是真的。其逆否命题是“不是无穷周期循环转型的构型不是E一图”，即非E—图的构形一定是有限次转型的构形。原命题是真的，其逆否命题也就是真的了。这就从理论上证明了无环形链的H—构形的转型次数是“有限的”是正确的。
因为“无上界”的“有限”实际上就是无“穷”或“无限”，所以这个“有限次”的上界值是多少，也需要确定。E—图转型的循环周期有三个：第一个是构形的类型在BAB—DCD—ABA—CDC四种类型间的转型周期是4；第二个是峰点位置的转型周期是5。因为该构形有5个围栏顶点，各个围栏顶点都做一次峰点，就是5次转型；第三个是构型的类型和峰点位置同时返回原来的类型和位置时的周期是4×5＝20。E—图每转型20次，就又返回到了原来的E—图。
已知无环形链的H—构形是属于非E—图的构形，也就一定不是无穷周期循环转型的构形（即既不是无穷周期循环转型的构形，也不是无穷不循环转型的构形）。
从E—图构形转型中可以看出，光是把第一个循环周期完成了，只进入了第二个循环周期还是不行的，还必须再看第二个循环周期能否完成（即能否进入第三个循环周期）。第二个循环周期是否能够完成，是一个很关键的地方。完成了，才能确定转型是产生了周期循环；完成不了，构形就会转化成可约的K—构形，转型就不会产生周期循环，就是一个有限次转型的构形。这里所说的循环周期能否完成，是指每转型20次，图是不是又返回到了原来的初始状态。
可以看出，要确定一个构形是否是无穷周期循环转型的构形，至少需要的转型次数要达到E—图构形或5—轮构形固有的循环周期20次转型的两倍，即2×20＝40次转型。达到并进入第三个循环周期者，即是无穷周期循环转型的构形；否则，达不到者，即为有限次转型的构形。
在这里，我们已经从理论上解决了非E—图构形的H—构形最大的转型次数的上界值的界是：不小于20次，又不大于40次。但这只相当于是一个猜想，还要经过进一步的证明是否是正确的。
13、对上面“上界值”结论的检验（实践检验）
E—图构形是可以向两个方向进行转型的，在两个方向转型的20次之内的41个构形中，每相隔20次转型的两个构形都是完全相同的，即是完成了一个循环周期的。在实际对E—图从一个方向的转型过程中，即就是看到了第20次转型结果已返回到了原图，这时我们并不能确定其就是以20次转型为周期循环转型的构形，还必须继续的进行转型，等到转型次数达到40次，出现了第二次返回到了原图时，才能确定其是周期循环转型的构形。E—图转型是这样，其他图的转型也是这样的。
我们在给一个非E—图的构形的转型时也是这样的。其逆时针转型是不会超过20次的，顺时针转型也是不会超过20次的，两个转型次数加起来也一定是不会超过40次的。我和张彧典先生都构造过转形次数大于20次以上的、但又小于40次的非E—图构形。
我们用了逆时针方向转型都需要21次转型的两个构形（如图26—1和图27—1），其顺时针方向转型分别需要3次转型和7次转型。其中一个构形的两个方向转型的转型次数之和是24次，另一个构形的两个方向转型的转型次数之和是28次，这说明了转型次数大于20次才可以转化成可约的K—构形而不出现循环转型的H—构形是存在的。


这两个构形在两个方向转型的转型过程中，每相隔20次转型的两个构形，虽然都是峰点颜色和两个同色顶点颜色都相同的同一类型的非E—图构形，但其中的各顶点的颜色却并不都是完全相同的。比如，我们所用的两个构形的原图分别如图26—1和图27—1，都是BAB型的构形。逆时针方向转型15次和18次后分别是图26—2和图27—2，顺时针方向转型5次和2次后分别是图26—3和图27—3。图26—2和图26—3中的两个构形，以及图27—2 和图27—3中的两个构形，都是同方向转型相隔20次的构形。虽然分别都是CDC型和ABA型，但图中却不是所有的顶点都有相同的颜色（如图26—2和图26—3中，左侧的多重菱形中就有中间的两个顶点的颜色不同，图27—2和图27—3中，右侧的多重菱形中也有中间的两个顶点的颜色不同），这也说明了转型次数达到20次，并不反回到原初始状态的H—构形是存在的。
以上两点都说明了无环形链的H—构形转型次数最大只能是在40次转型之内就可以解决问题的，转型次数的最大值是40。
这里又从着色实践中证明了上面提出的，非E—图构形的H—构形最大的转型次数的上界值，是不小于20次的猜想是正确的。
14、非E—族的H—构形最大转型次数上界值的确定（理论证明）
首先要明确这种非E—图的H—构形是已经经过证明是可约的，且转型次数一定是有限的。这是根据E—图构形转型的无穷周期循环性，用“原命题的逆否命题与其原命题同真同假”的逻辑关系进行判断证明的。现在这里主要是要确定这个“有限的”上界值是多少的问题，而不是研究这种构形是否是可约的问题。
H—构形是可以向逆时针方向和顺时针方向两个方向进行转型的。一个构形设逆时针方向转形了m（m≤20）次，达到了转型的终了（指空出了颜色给待着色顶点着上时），顺时针方向转型了n（n≤20）次，也达到了转型的终了。那么两个终了构形（图）之间（包括两个终了图）一共有m＋n＋1个构形（图），式中的这个“1”就是指原构形。其中，有m＋n＋1－2×3个构形（图）是H—构形（因为各个方向转型的最后三个图都不是H—构形而是K—构形，所以要减去2×3）。
那么，分别从这两个转型的最后第四个构形开始，按相反方向进行转型，一直达到转型终了时，应是m＋n＋1－4次的转型（或交换。最后的两次所谓的“转型”实际上是属于连续的移去两个同色的K—交换）。这就是该构形当有一个方向进行一次转型就转化为可约的K—构形时，而向另一个方向转型时的最大转型次数。我们已经找到了转型次数为25次的具体构形，证明了其转型的最大次数是大于5—轮构形的固有周期（即5—轮构形的围栏顶点的转型周期）20次的，以及也大于E—图构形的转型周期20次的构形是存在的。那么，现在要问，还有没有比这个转型次数更大的构形呢？最大的转型次数是多少呢？
我们在转型过程中发现，这种转型次数大于20次的构形，经过20次转型，属于原E—图中的所有顶点都回到了原来的初始状态，而在E—图中所增加的顶点（增加了这些顶点后，E—图就转化成了非E—图的H—构形了。如前面的图26—1和图27—1，都是在E—图的基础上增加了两个顶点的），却没有回到初始状态。这说明构形虽然进入了E—图构形的第二个循环周期，但整个构形还没有回到初状态，根本不能判断是否是产生了循环转型。至此，E—图构形的第三个循环周期还没有到来，也是不可能到来的。因为我们所研究的这种构形已经证明是在有限次转型之内，就可以转化成K—构形，是可约的，根本就不可能产生循环转型的。
既然E—图的第三个循环周期不可能到来，那就只能在E—图的第三个循环周期到来之前的第40次转型前，转型过程就必须结束。采用反证法：如果说转型过程有可能进入E—图构形的第三个循环周期之内，就说明原E—图的转型就进入了周而复始的E—图构形的无穷周期循环了，不管在E—图中增加的顶点反回不反回到原着色状态，都说明整个图的转型是无穷的了。这与我们在这里所研究的构形本身是有限次转型就可以转化成可约的K—构形的条件则是格格不入的。所以说该构形的转型是不可能进入E—图的第三个循环周期的。
既然进入不了E—图的第三个循环周期，就说明了我们原来所说的“那就只能在E—图的第三个循环周期到来之前的第40次转型前，转型过程就必须结束”这一假设还是正确的。最大的转型次数就只能是40次了。这就是把非E—图的H—构形最大转型次数的上界值确定为40次转型的原因。
这里又从理论上证明了上面提出的，非E—图构形的H—构形最大的转型次数的上界值，是不大于40次的猜想是正确的。
15、四色猜测是正确的
至此，我们就从理论（逻辑判断：非E—图构形的H—构形一定是可4—着色的）和着色实践（构形的可约性：平面图的各种不可避免构形都是可约的）以及对所得结论的检验（最大转型次数：非E—图的H—构形在最多在40次转型之内一定是可以转化成可约的K—构形的）三个方面都说明了四色猜测是正确的。
四色猜测从1852年提出至今已有170年的历史了。在经过了27年艰苦趴涉后，终于在1879年由坎泊给出了第一个证明，但只是证明了可以通过坎泊的颜色交换技术，直接从围栏顶点中空出某一种颜色来、给待着色顶点着上的K—构形都是可约的（坎泊链法）。
后来再过了11年后的1890年，赫渥特给出了一个不能通过坎泊的颜色交换技术，直接从围栏顶点中空出任何一种颜色来的、且图中有一个经过了双环交叉链的两个末端顶点C和D的C—D环形链的赫渥特图（即H—图或H—构形），指出了坎泊的证明有“漏洞”，但当时并没有解决H—图（H—构形）的可4—着色的问题。
再过了31年后的1921年，埃雷拉也构造了一个不能通过坎泊的颜色交换技术，直接从围栏顶点中空出任何一种颜色来的、图中有一个经过了双环交叉链的共同起始顶点A的A—B环形链的埃雷拉E—图，与H—图都同属于H—构形。
又过去了14年后的1935年，欧文对埃雷拉E—图进行了可4—着色（正切链法）；后来再经过了57年的1992年，我国的雷明，董得周，还有英国的米勒等人，都分别用不同的方法对赫渥特图，进行了可4—着色（米勒的方法雷明叫它转型法，张彧典叫它H—换色程序和颠倒法）；同年，我国的敢峰在不知还存在有E—图的情况下，独立的用“四环演绎法”也构造了E—图，并解决了该图的可4—着色的问题；又过了18年后的2010年，我国的张彧典也独立的构造了E—图，也用与欧文、敢峰同样的方法对其进行了可4—着色（张把这一方法叫Z—换色程序）；2010年雷明在看到了E—图后，也用了与他自已解决H—图类似的方法（雷明叫其断链法）对E—图进行了可4—着色。10年后的2020年前后，雷明和张彧典分别又证明了另外一种没有任何环形链的H—构形（E—图中有环形的A—B链，H—图中有环形的C—D链），都可以在有限次的转型或颠倒内解决问题。
至此，已标志着平面图的所有的5种不可避免构形，在各种情况下的类型不但都已经完备，并且已都是可约的了。现在就可以堂堂正正的说四色猜是正确的，是可以作为四色定理应用的了。

雷  明
二〇二二年五月三十日于长安

雷明85639720

，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，