用两种方法分别证明四色猜测是正确的

雷明85639720

用两种方法分别证明四色猜测是正确的
雷    明
（二〇二三年五月一日）

【摘  要】四色猜测也叫四色问题。是专门研究关于对地图中行政区划的染色问题的。由于地图是属于图论中的“无割边的3—正则的平面图”，所以给地图中面（行政区划）上的染色也就是对地图的对偶图——极大平面图——的顶点着色。极大平面图的四色问题解决了，不仅只是证明了地图四色猜测是正确的，同时还可以说明任意平面图的四色猜测也是正确的。因为能够可4—着色的极大平面图，经去顶和减边后，所得到的任意平面图的色数只会减少而不会再增加。
【关键词】四色猜测  四色问题  待着色顶点  构形  不可避免顶点    坎泊链法  关键顶点  双环交叉链  待着色顶点移动  围栏顶点中空出颜色  断链交换法  易着色构形  难着色构形

一，        有关术语的定义及说明。
1，平面图的构形。
①面图的构形。还剩一个顶点未进行4—着色的色图就叫平面图的构形。这个未着色的顶点叫待着色顶点，用Ⅴ0表示。与Ⅴ0相邻的顶点叫围栏顶点。
②易着色构形与难着色构形。用d表示某一个顶点所连边的条数（即度），则有d≥0。用c表示与某一个顶点相邻的顶点所占用的颜色数，则有1≤c≤4。
当待着色顶点Ⅴ0的度d≤3（这时c也一定≤3）或者虽然Ⅴ0的度d≥4但c却仍然≤3时的构形叫易着色构形（可直接着色构形或终局构形）。
当待着色顶点Ⅴ0的度d≥4且c又＝4时的构形叫难着色构形（非直接着色构形或困局构形）。
③解决四色问题的关链。从以上可以看出，如何把难着色构形转化成易着色构形是证明四色猜测，解决四色问题的关键。解决的方法有待着色顶点移动法，围栏顶点空出颜色法，或两者混合使用的方法（各方法在后面将分别谈到）。
2，平面图的不可避免构形。
①平面图的不可避免构形。待着色顶点Ⅴ0的度在0≤d≤5之间的六种构形就是平面图的不可避免构形。因为任何平面图中都一定会至少含有一个度是d≤5的顶点的。也就是说，任何一个平面图中可以不含有度是d≥6的顶点，但必须至少含有一个顶点的度是d≤5的。或者说所有顶点的度都是d≥6的平面图是不存在的。
②平面图的不可避免顶点。既然平面图中至少要含有一个度是d≤5的顶点，那么d≤5的顶点也就是平面图的不可避免顶点。所以，以不可避免顶点为Ⅴ0的构形也就是平面图的不可避免构形了。
③平面图着色时一定可以把待着色的顶点Ⅴ0放到不可避免顶点之上。由于以上原的因，所以在着色时一定是可以将待着色顶点V0放到不可避免顶点之上的，特别是放到了d≤3的顶点之上时，就可以给V0直接着色了。若图中沒有d≤3的顶点，至少也是可以把Ⅴ0放到d＝4或d＝5的顶点之上的。万一没有把V0放到不可避免顶点之上，还是可以通过待着色顶点移动的办法，把Ⅴ0移动到不可避免顶点之上的。
3，解决难着色构形的方法。
①待着色顶点移动的方法。把不可直接着色的构形中围栏顶点使用次数最少的一种颜色直接给Ⅴ0着上，就会在原来的围栏顶点中新产生一个或多个新的待着色顶点Ⅴ0，这样Ⅴ0就移动了一步。重复上面的操作，就可以把V0移动到图中的任何一个顶点上去。
②从围栏顶点中空出颜色的方法。上面的待着色顶点移动法的Ⅴ0是移动的，而这里的从围栏顶点中空出颜色的方法中，Ⅴ0却是固定不变的。该方法又有两种，一种是坎泊链法，只适用于K—构形，另一种是断链交换法，只适用于H一构形。
4，坎泊链法。
①适用性。坎泊链法是属于从围栏顶点中空出颜色的一种，是在1879年由坎泊创造并首先使用的。它只适用于解决无双环交叉链的构形的可4一着色问题。
②色链。色链是用两种颜色交替着色的一条道路，简称链。把链中两种颜色相互调换，可以达到改变链中任一顶点颜色的目的。
③对角链。如果链中的两种颜色是由围栏顶点的两个对角顶点的颜色构成的，就叫对角链。对角链从一个对角开始一直连到另一个对角时，叫连通的对角链（简称连通链）。对不连通的对角链换色的结果，就使得围栏顶点中减少了某一种颜色的使用次数。为从围栏顶点中空出颜色创造了条件。
④度最大时的不可避免构形的围栏中只有5个顶点，全部占用完四种颜色时，最多也只可能有一种颜色是使用了两次的（这种构形的围栏顶点我们一般用按1B—2A—3B—4D—5C—1B为次序的顺时针旋转方向来表示）。所以坎泊就认为最多进行两次换色就可以解决平面图任何不可避免构形的可4一着色问题。但是他错了。他的证明只解决了无双环交叉链的构形的4—着色问题，而却遗漏了含有双环交叉链的一类难着色构形。没有证明这类构形是否可以4—着色。
⑤这种解决无双环交叉链的构形可4—着色的方法是坎泊提出并首先使用的，所以就叫坎泊链法。把用坎泊链法所能解决可4—着色的无双环交叉链的构形就叫K—构形（K是坎泊英文名字的第一个字毌）。
5，含有双环交叉链的构形的发现与解决。
①        个含有双环交叉链的构形的发现。
1890年赫渥特首先发现了坎泊证明中的漏洞，并构造了一个含有双环交叉链A—C和A—D的构形——H—图，其中含有经过了双环交叉链两个末端顶点的C—D环形链，把双环交叉链的共同起始顶点和交叉顶点分隔在了C—D环形链的两侧，互不连通，不能用坎泊链法空出任何颜色解决问题。可惜的是当时赫渥特和坎泊都未能用别的方法解决这个问题。
1921年埃雷拉也构造了有双环交叉链A—C和A—D的构形——E—图，其中却含有经过了双环交叉链的共同起始顶点的A—B环形链，并把C—D链分隔在了A—B环形链的两侧，也互不连通，也不能用坎泊链法空出任何颜色解决问题。
1992年敢峰和米勒的团队分别在不同的国冢，用不同的方法都构造了与埃雷拉E—图相同的构形（敢峰叫他的图为＂终极图＂，米勒团队的图我们叫它M—图）。
2020年雷明又构造了含有双环交叉链A—C和A—D的构形——L—图，图中既不含有A—B环形链，又不含有C—D环形链。A—B链和C—D链都只是一条直链而不成环状。
H—图，E—图和L—图，这三种构形中都含有双环交叉链，与K—构形是大不相同的。由于这种构形是赫渥特最早发现并构造的，所以暂时就先把这种含有双环交叉链的构形叫做H—构形吧。
②这几个含有双环交叉链的具体图的着色办法。
1935年欧文研究了E—图，对一条叫做“正切链”的色链进行了交换（实际上也就是进行断链交换），断开了双环交叉链，使H—构形转化成了可约的K—构形。
1992年雷明与董德周分别独立的对H—图进行了研究，分别用对C—D环形链内外任一侧的A—B链进行了交换（也还是断链法），也断开了双环交叉链，使构形由H—构形转化成了可约的K—构形。
1992年敢峰也独立的用可控换色的演绎方法又构造了与E—图完全相同的“终极图”，并用与断链交换法相同的方法对其进行了可4—着色。
1992年米勒团队曾企图用“颠倒法”（也就是使构形的峰点变化的转型法）对四色猜测进行证明，但他们用颠倒法对他们的M—图（也即是E—图）进行了无数次的颠倒后，仍不能得出可4—着色的结果。于是他们就又放弃了企图用颠倒法证明四色猜测的想法。
2010年张彧典总结了米勒的教训，发现在对E—图的每一步颠倒的结果中，都含有一条A—B环形链，且都是H—构形，颠倒次数再多，也是解决不了问题的。于是他丢弃了米勒的颠倒法，改用在A—B环形链的任一侧交换C—D链的办法，使双环交叉链断开，解决了E—图的可4—着色问题。
紧接着，后来又在此基础上，雷明又根据张彧典的研究，把解决有环形链的H—构形的这一方法起名叫做断链交换法。因为在这一交换后，就使得双环交叉链受到了破坏，使构形由H—构形转化成了可约的K—构形。
2022年雷明还发现了有环形链的H—构形与无环形链的H—构形间是可以相互转化的规律。先把无环形链的H—构形（L—图）转化成有环形链的H—构形，再用断链法去进行解决。
6，断链交换法。
（1）适应性。断链交换法也是属于从围栏顶点中空出颜色方法中的一种，是从1935开始年至今，在漫长的近90年里，广大的四色爱好者从对H—图，E—图及L—图的4—着色过程中摸索和总结出来的，仅适用于解决有环形链的H—构形。
（2）构成H—构形的必要条件。前面已说过，是暂时把有双环交叉链的构形叫做H—构形。在研究过程中发现，有些构形中虽然含有双环交叉链，但也可以用坎泊链法，连续的移去两个同色。如四个“九点形”构形中就有三个是可以连续的移去两个同色的构形。因此可以说，有双环交叉链只是构成H—构形的必要条件，而并非充分条件。也就是说，沒有双环交叉链，不可能构成H—构形，但有了双环交叉链，却不一定都是H—构形。
（3）H—构形的重新定义。把用坎泊链法不能从围栏顶点中空出任何一种颜色的构形叫做真正的H—构形。
（4）关键顶点。H—构形中双环交叉链的共同起始顶点和交叉顶点，以及两链的末端顶点，这四个顶点就是关键顶点。其中只要有任何一个关键顶点的颜色发生了变化，双环交叉链都会断开。构形由H—构形转化成可约的K—构形。
（5）相反链。两种颜色的顶点的连续交替序列可构成一条色链。另两种颜色的顶点的连续交替序列也是另一条色链。这两条沒有相同颜色的色链，就是一对相反链。两条相反链是不能相互穿过的。若其中有一条是环形链时，则其相反链一定是两条，并被分隔在环形链的两侧。每一侧的相反链分别都是可以交换的。这就为断链交换法的实施创造了条件。如果环形链和其一侧的相反链都通过了关键顶点，则交换环形链一侧的相反链，一定会使双环交叉链断开。成为无双环交叉链的可约的K—构形。
7，从围栏顶点中空出颜色的着色方法。
以上4中讲的只适用于K—构形的坎泊链法和6中讲的只适用于H一构形的断链交换法都属于从围栏顶点中空出颜色的着色方法，只是适用的范围有所不同。前者适用于K—构形，后者适用于H—构形。二者总共包含了平面图的所有不可避免构形。解决四色问题就是要证明所有的不可避免构形都是可约的，下面就来进行证明。
二，四色猜测的证明。
1，用待着色顶点移动的方法证明四色猜测。
①用这种证明方法证明，不一定非得要把待着色顶放到不可避免顶点之上。既然是待着色顶点移动法，当然一定是可以把待着色顶点移动到不可避免顶点之上的。
②由于构形中除了待着色顶点之外的其他顶点都是进行了可4—着色的顶点，因此与其他任何顶点相邻的顶点所占用的颜色数一定都是c≤3的。
③当把Ⅴ0移动到了d≤3的不可避免顶点上时，就是易着色的构形，直接着色就可以了。
④当要把Ⅴ0移动到d＝4的不可避免项点上去时，有两种情况。
一种情况是该顶点的4个围栏顶点只占用了两种颜色的情况，两对对角顶点的颜色分别都是相同的，四个围栏顶点均处在一个同等的地位上，两侧都与着有相同颜色的两个围栏顶点相邻。Ⅴ0从任一个围栏顶点移入都可以。这时围栏顶点只占用了3种颜色，把第4种颜色给Ⅴ0着上即可。该图4—着色完成。
4个围栏顶点已占用了3种颜色的情况，两对对角顶点只有一对对角顶点的颜色是相同的，另一对对角顶点的颜色却不相同。但这一对颜色不相同的两个对角顶点的两侧也都与着有相同颜色的另外两个围栏顶点相邻，也处在一个同等的地位。这种情况下，Ⅴ0从这两个单色围栏顶点中的任何一个顶点移入也都是可以的。这时的围栏顶点也只占用了3种颜色，把第4种颜色给Ⅴ0直接着上也就可以了，该图的4—着色也就完成了。
从以上的证明还可以看出，Ⅴ0要移动上去的顶点，其围栏顶点所占颜色数是2（双色）时，是一定可以把Ⅴ0移动上去的，且V0一定可以着以四种颜色之一。这一点不仅适用于d＝4的不可避免顶点，同样也适用于d＞4的任何偶度顶点。
⑤当要把Ⅴ0移动到d＝5的不可避免顶点上时，其围栏顶点一定是占了3种颜色，且一定有一个顶点是单色的，把V0从这个单色的围栏顶点移入即可，围栏顶点仍是只占用了3种颜色，把第4种颜色给V0着上即可完成该图的4—着色。
从以上也可以看出，V0要移动上去的顶点，其围栏顶点中只要有且仅有一个顶点是单色顶点时，就一定可以把V0移动上去，Ⅴ0也一定能够着上四种颜色之一。同样的，这一点也不仅只适用于d＝5的不可避免顶点，也适用于d＞5的任何奇度顶点。
②        色猜测是正确的。
到此，用待着色顶点移动的方法证明四色猜测的过程就结束了，只要把待着色顶点V0向平面图的不可避免顶点移动，都是可以4—着色。四色猜测是正确的。
2，用从围栏顶点中空出颜色的方法证明四色猜测。
①这种证明方法强调的是待着色顶点V0一定是要落在不可避免顶点之上的构形。如果不是，可用待着色顶点移动的方法，把Ⅴ0移动到不可避免顶点之上。
②用坎泊链法证明K—构形是可约的。
这一方法是坎泊在1879年已经证明过了的，不含双环交叉链的K一构形都是可4—着色（可约）的，这里不再重复。
③含有双环交叉链的构形只可能出现在度为d＝5的不可避免构形中。含有双环交叉链的构形中有一部分是可以用坎泊链法连续的移去两个同色的构形，我们把它仍归于K—构形。而另一部分含有双环交叉链的构形才是真正不能用坎泊链法从围栏顶点中空出任何一种颜色的H—构形，需要用别的办法去解决。
④用断链交换法证明含有环形链的H一构形是可约的。
这种方法是从1935年一直到现在，在漫长的对H—图，E—图，M—图及终极图的4—着色过程中总结出来的。只适用于解决有经过了关键顶点的环形链的H—构形。有A—B环形链者交换C—D链，有C—D环形链者交换A—B键，都可以使双环交叉的A—C链和A—D键断开，使H—构形转化成可约的K—构形。
⑤用有，无环形链的H—构形可以相互转化的特点，证明无环形链的H—构形也是可约的。
从图中可以看出，在无环形链的H—构形中，A—B链和C—D链都是直链且是单条，各条中均至少有一个这样的顶点，当把其所着的颜色改成其相反链中的某种颜色后，其相反链就会变成环形链。并且这种过程是可逆的。这就是有，无环形链的H—构形可以相互转化的原理。
③        色猜测是正确的。
到此，平面图的各种不可避免构形都是可约的了。用从围栏顶点中空出颜色的办法证明四色猜侧的过程也就结束了。四色猜测是正确的。
3，以上用两种方法都证明了四色猜测是正确的。

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