一个更加通俗易懂的证明过程：不可免构形可约法证明四色猜测（一）

雷明85639720

不可免构形可约法证明四色猜测（一）
——一个更加通俗易懂的证明过程
雷  明
（二○一八年五月二十三日）

1、把一个地理学中给地图区域的染色变成一个给图论中平面图顶点着色的数学问题
四色猜测也叫四色问题。是在对地图染色的过程中提出的。说的是把一个平面分成若干部分，给每一部分都着上不同的颜色，使得有公共边界线相邻的两部分都不用同一颜色，最多四种颜色就够用了。这应是一个地理学中的问题。
研究四色问题时,往往都假定：① 把平面所分成的若干个部分中，不存在一个部分包围另一个部分的情况，即不存在实际地图中的“国中之国”的情况；② 把每一个部分都看成是一个单独的区划，即不存在实际地图中的“一国多地”的情况；③ 不存在三条以上边界线相交于一点的情况，即与实际地图中的各顶点都只是由三条边界线相交而成的“三界点”是相同的情况。
以上的几条假定都是不会影响到四色猜测的证明的。① 因为实际地图中的“国中之国”这个国家的外围只有一个国家，只能占用一种颜色，“国中之国”仍有三种颜色可任意选择染色，并不会影响到对其外围国以外的国家的染色；② 因为没有公共边界的不同区域是可以用同一种颜色染色的，所以我们可以把实际地图中的“一国多地”的国家看成是不同的几个“国家”，着上同一种颜色也就可以了，并且这也是一定可以办到的；③ 关于多于三条以上边界线相交于一点（如图1，a）的情况，我们可以假设在这个公共点处有一个“小区域”（如图1，b），这样，一个大于三条边界线相交的顶点，就变成了与其相交的边界数有相同数目的“三界点”，而不存在三条以上边界线相交于一点的情况了。这就成了一个所有顶点都是3—度的3—正则平面图。

染完色以后，把这个“小区域”再去掉，地图中也不会存在两个有公共边界线的区域染有相同颜色的情况，地图的色数也只会因去掉了这个“小区域”而减少，而绝不会再增加，仍是符合四色猜测的要求的。
地图是一个无割边的3—正则平面图，给地图的面（包括外部的无限面）的染色，也就相当于给地图的对偶图的顶点着色。把地图中的每一个区划（包括海洋区划在内）的中心城市用一个“顶点”来代表，在有公共边界线相邻的两个区划的中心城市间，都修有穿过该两个区划的公共边界线的铁路或公路相连（沿海区划与海洋区划的“中心”用“航线”连接），这样就得到一张地图的对偶图（如图２中的粗线所示），也是一个极大平面图，其所有的面均是三角形面。
现在再对这张地图的对偶图的顶点着色，也就相当于给地图的区域的染色。这就把一个给地图的面上的染色的地理学问题，变成了数学中对图论中平面图的顶点着色的数学问题了。地图四色猜测也就变成了平面图的四色猜测了。现在，对平面图的四色猜测可以这样来表述：即是任意平面图的色数都不大于4。

从图2中可以很显然的看出,研究图的顶点与顶点间的关系，研究图的顶点着色，比研究图中面与面间的关系，研究图的面的染色要容易得多。只要证明了极大平面图的色数不大于4，那么对极大平面图经去点和减边得到的任意平面图的色数却只会减少而不会再增加，四色猜测也就得到了证明是正确的。
2、不可免构形可约法证明四色猜测的原理
如果一个平面图中还剩下一个顶点未着色，其他的顶点都已用四种颜色分别着色，并且符合顶点着色的要求。即除了该未着色顶点外，其他的顶点都是可4—着色的。如果在与未着色顶点相邻的顶点未占用完四种颜色的情况下，能直接给该未着色顶点着上图中已用过的四种颜色之一；或者在与未着色顶点相邻的顶点已占用完了四种颜色的情况下，通过颜色调整（即颜色交换），可以给该未着色顶点着上图中已用过的四种颜色之一；该平面图的4—着色就已经完成。把这样的只有一个未着色顶点的，且其他顶点均已进行了4—着色的图就叫做构形。构形中未着色的顶点叫待着色顶点，与待着色顶点相邻的顶点叫围栏顶点，简称围栏。能直接的或通过颜色调整后，给待着色顶点着上图中已用过的四种颜色之一，就叫做构形可约，即构形是可4—着色的。
构形和构形可约的概念是坎泊在1879年首先提出并使用的。构形并不是一个具体的图，因为在构形围栏顶点以外的顶点的数目，以及顶点与顶点之间的相邻关系，都可以是任意的。所以在平时表示构形时，只画出待着色顶点和围栏顶点就可以了。可见构形实际上就是一个轮图，轮的轴心顶点就是待着色顶点，轮的轮沿顶点就是围栏顶点。只要能证明某一构形的待着色顶点可以着上图中已用过的四种颜色之一，该构形就是可约的。但是待着色顶点的度（也即与待着色顶点相邻的顶点数或轮沿的顶点数）却可以是任意的，要证明这任意多种（无穷多的）度的构形是否可约，可真是有难度的，而且也是不可能的。
如何解决这一问题呢？ 1879年坎泊证明了任何地图中至少都存在着一国与两国相邻，一国与三国相邻，一国与四国相邻，一国与五国相邻4种情况中的一种情况，并认为这４种情况就是地图中的不可避免构形。即地图中不存在所有国家都与六个或六个以上的国家相邻的情况。这就为把一个无穷的问题转化成一个有穷的问题打下了基础。正好，在图论中也可以证明任意平面图中一定至少存在着一个顶点的度是小于等于5的。也即平面图中不存在所有顶点的度都是大于等于6的情况。坎泊指出的存在在地图中的4种国与国相邻情况的对偶图正好也就对应的是一个轮的轴心顶点的是度小于等于5的4种轮。
这样，平面图的不可避免构形对应的就应是轮沿顶点数小于等于5的轮了，即0—轮（K1图），1—轮（K2图），2—轮（2—重K3图），3—轮（K4图），4—轮和5—轮。只要证明了这六种不可避免的构形是可约的，也就是等于证明了平面图的四色猜测是正确的。这就是不可免构形可约法证明四色猜测的基本原理。
当我们证明了度小于等于5的轮构形都是可约的后，在给一个具体的平面图着色时，总是从图中可以找到一个度小于等于5的顶点，并将其留作为最后一个待着色的顶点。再分析该待着色顶点属于那种构形类型，并按照解决该类型不可免构形的办法，给这个最后的顶点着上图中已用过的四种颜色之一，就完成了给一个平面图的4—着色。
3、1879年坎泊对四色猜测的证明
因为0—轮构形，1—轮构形，2—轮构形，3—轮构形的围栏顶点所占用的颜色数均是小于4的，所以都是可以直接给待着色顶点着上第四种颜色的。也即这些构形都是可约的。而对于4—轮构形，1879年坎泊用他所创造的颜色交换技术也证明了4—轮构形是可约的。所谓颜色交换技术，就是把一个用两种颜色交替着色的序列（道路）中各顶点的颜色进行相互交换，以达到改变该道路中任何一个顶点颜色的目的。坎泊就把这种序列叫做色链，简称链。
坎泊认为4—轮构形的围栏顶点占用了A，B，C，D四种颜色（如图３），两对对角顶点的颜色构成的色链一定是相反链，即两条链中没有共同颜色的链就是相反链。而相反链是不可能相互穿过的（因为两链中没有共同的颜色），所以只要有对角A和C的对角链A—C是连通的时（如图3，b），则对角B和D的对角链B—D一定是不会再连通的。这样，从B色顶点或从D色顶点起交换B—D链，就可以空出一种颜色B或D来，给待着色顶点V着上（图中未画出待着色顶点V，这是一种隐形画法）。这就证明了4—轮构形是可约的。

四种颜色A、B、C、D可能构成的色链种数是从四种元素中取出两种进行组合的组合数，即链的种数等于4×（4－3）÷2＝6，即A—B，A—C，A—D，B—C，B—D，C—D六种。其中A—B和C—D，A—C和B—D，A—D和B—C各是一对相反链（相反链中没有共同的颜色），两相反链是不能相互穿过的；A—B，A—C，A—D三种；B—A，B—C，B—D三种；C—A，C—B，C—D三种；D—A，D—B，D—C三种，是四组相邻链（相邻链是链中有一种共同颜色的链），相邻链则是可以相互穿过的。
坎泊在证明5—轮构形时，只证明了一部分情况（如图４中的ａ，ｂ，c等情况），且都是可约的；却把另一种情况（如图4，d的情况）遗漏了。在过了11年后的1890年，赫渥特构造了一个图，指出了坎泊的漏洞所在。但虽然发现了坎泊漏洞，赫渥特和坎泊二人当时却都没有能把这个漏洞弥补上。不但没有解决具有赫渥特图特征的一类构形的可约性问题，就连这一个具体的赫渥特图也没有进行4—着色。直到一百多年后的1990年前后，才有我国的雷明，懂德周，以及英图的米勒等在赫渥特原着色的基础上，各用不同的方法对赫渥特图进行了4—着色。方法虽然不同，但都没有离开坎泊所创的颜色交换技术。另外，还有我国的许寿椿教授等在计算机上用自已编写的算法（程序），也对赫渥特裸图（即一个顶点也没有着色的图）进行了4—着色。这些都为解决5—轮构形的可约性，以及解决四色问题，打下了坚实的基础。

为了研究方便，我们在以后的证明中把坎泊已证明过的、是可约的构形统一叫做K—构形，而把坎泊未证明的、具有赫渥特图相同特点的图均叫做H—构形。
4、1890年赫渥特构造的H—构形图的特点


图5，a是赫渥特构造的赫渥特地图，其对偶图是图5，b。若只把该图主要的顶点和边留下，该图简化后就是图6。从图5和图6中可以看出，两图中有连通的A—C链和A—D链，这两条链是相邻链，有共同的起始顶点2A和交叉顶点8A，由于该两链都是连通链，所以不能进行交换而空出A、C、D三色之一给待着色顶点V；若企图想移去两个同色B，但当交换了一条关于B的链时，虽然移去了一个B，但却又就会产生从另一个B色顶点到其对角顶点的连通链，而不可能同时移去两个B。产生这一情况的主要原因就是因为两条连通的相邻链A—C和A—D在中途相交叉的结果。
这就是说，在这种双A夹B型（或BAB型）的5—轮构型中，在四种颜色所能构成的六种链中，已有A—C、A—D、B—C、B—D四种不能交换，且它们都属于由5—轮的对角顶点的颜色构成的对角链；剩下的可交换的链，就只是由5—轮的轮沿顶点中由1B—2A—3B的颜色构成的A—B邻角链和轮沿顶点4D—5C的颜色构成的C—D邻角链了。
我们还发现，该构形中由5—轮的相邻轮沿顶点4D—5C的颜色构成的C—D链是一条环形链，把图中的A—B链分隔成了互不连通的两部分，由5—轮的对角顶点1B—2A—3B的颜色构成的A—B链只能处在环形的C—D链的一侧。这时交换环形链C—D任一侧的C—D链，都可以使图中连通且相交叉的A—C和A—D链断开，变成非连通链。彻底的产除了生成H—构形的条件。构形也就变成了可约的K—构形了。在这里，仍然用的是坎泊的颜色交换技术。
当年赫渥特和坎泊为什么又不能给赫渥特图进行4—着色呢，因为他们一味的想要移去两个同色B，而没有看到，在交换了一个关于B的链后，却产生了从另一个B色顶点到其对角顶点的连通链，而不能移去两个同色B。连通链是不能进行交换的。今天,大家都说赫渥特通过他的图否定了坎泊的颜色交换技术，我认为这种说法是不对的。以上雷明等几个人对赫渥特图的4—着色，不还都用的是坎泊的颜色交换技术吗。本来坎泊的颜色交换技术是在非连通链的情况下,才能进行交换而空出颜色的，而赫渥特却硬是要交换连通的链，当然也就不可能空出颜色来。
是不是有两条连通且相交叉的A—C和A—D链的图都不能同时移去两个同色B呢，不是的。如图7的三个构形（图），只要在两链的交叉顶点8A和两个同色顶点1B或2B之间，有一个B色顶点与8A有边直接相邻，这样的图就是可同时移去两个同色B的构形。图7，a先从1B开始交换B—D 链，再从3B交换B—C链；图7，b先从3B开始交换B—C 链，再从1B交换B—D链；图7，c则无论先从那个B色顶点开始交换关于B的色链；都是可以同时移去两个同色B的。


还有没有与赫渥特图有相同特征的构形呢，有。图8中各图就是代表不同类型的H—构形。由于A—B链和C—D链是一对相反色链，所以这两条链是不可能相交叉的。在H—构形中，经过1B—2A—3B的A—B环形邻角链和经过4D—5C的C—D环形邻角链，① 要么只存在A—B或C—D一条（如图8，a和图8，b），② 要么两条都存在但不相交叉（如图8，c1和图８，c2），③ 要么一条也不存在（如图8，d1和图8，d2），④ 要么是另一种既不存在环形链，但又有一条以A—B链作对称轴的对称构形（如图8，e1）。

经过1B—2A—3B的A—B环形邻角链和经过4D—5C的C—D环形邻角链的相互关系，在H—构形中除了以上这四种情况外，再就没有别的情况了。这就是我所构造的H—构形的不可免集，而且是一个完备集。

图８，ａ是有一条经过５—轮轮沿顶点1B—2A—3B的环形的A—B邻角链的H—构形；图8，b是有一条经过5—轮轮沿顶点4D—5C的环形的C—D邻角链的H—构形；图８，c是有两条环形链但又不相交叉的H—构形；图8，d是没有任何环形邻角链的构形，图8，e是没有任何环形邻角链但有一对称轴是A—B链的对称的H—构形。他们都分别代表着一类有共同特征的、且解决方法各不相同的H—构形。

下面我们就来分别谈变各种情况的H—构形的解决办法，如果它们都是可约的，都可以给其中的待着色顶点V着上图中已用过的四种颜色之一，就可以证明四色猜测是正确的。
5、各类H—构形的解决办法
要解决H—构形的可约性问题，就必须知道H—构形是因什么原因而生成的。破坏了其生成的条件，当然问题也就解决了。前已述及，产生生成H—构形的条件是因为有连通且相交叉的A—C和A—D两条对角链，如果没有这两条对角链，自然问题也就得到了解决。既然H—构形已经存在这样的两条对角链，现在我们的任务就是要想一切办法把已连通的对角链断开，使构形成为没有连通对角链的，或者即就是还有连通的对角链，但在中途却不再相交叉的构形。这样，问题就可得到解决，H—构形就能成为可约的K—构形。其解法分别是：
A类H—构形（即图8，a、图8，c1和图8，c2）：图中都有一条环形的邻角链A—B，可以交换A—B环任一侧的C—D链，可使得A—C链和A—D链断开，图变成K—构形而可约。这个构形应该说是雷明先生在研究赫渥特图的特点和解决办法时构造出来的。
B类H—构形（即图8，b和图8，c1）：图中都有一条环形的邻角链C—D，可以交换C—D环任一侧的A—B链，也可使得A—C链和A—D链断开，图变成K—构形而可约。1890年赫渥特构造的赫渥特图就是具有这种构形特征的图。1990年，雷明先生也就是用这样的方法，在赫渥特原着色的基础上给赫渥特图进行4—着色的。
图8，c1和图8，c2从表面上看，都有环形的A—B链和环形的C—D链，好象应是单独的一类。但图8，c1中的A—B链和C—D链都是邻角链，任意的归入A类和B类都可以，任意的交换A—B环两侧的C—D链，或者任意的交换C—D环两侧的A—B链，都可以解决问题；而图8，c2中却只有环形的A—B链是邻角链，图中环形的C—D链却不是邻角链，也没有经过顶点4D—5C，只能归入A类而不能归入B类。图8，c2只可以任意交换A—B环两侧的C—D链，使图变成K—构形而可约；但若任意的交换了C—D环两侧的A—B链，图则仍是一个不可约的H—构形。图8，c2就是1900年前后我国的敢峰先生和英国的米勒分别构造的的敢峰—米勒图。敢峰先生用与以上相同的方法对其已进行了4—着色，而米勒却没有着色成功。后来我国的张彧典先生在研究米勒的所谓“颠倒”的着色方法时，在其2010年出版的《四色问题探秘》一书中，也用与以上相同的方法对敢峰—米勒图进行了4—着色。敢峰—米勒图的着色方法也只能是任意交换A—B环两侧的任一条C—D链，使图变成可以同时移去两个同色B的K—构形。
这里我们把解决A类H—构形和解决B类H—构形交换邻角链的方法叫做断链交换法，因为该交换的目的不是为了空出颜色，而是为了使A—C链和A—D链断链。以区别于坎泊只把颜色交换技术应用于交换对角链而只能空出颜色的一种用途。
C类H—构形（即图8，d1和图8，d2）：图中没有任何的环形链，且A—B链和C—D链也都只是一条。这就是张彧典先生在其《四色问题探秘》一书中的第八构形。该构形中A—B链和C—D链也都成了不可交换的链了，即就是交换了，也只相当于把图中所着的颜色交换了一下相互的位置，图将仍然是一个H—构形。如何办？还是有一条路是可以走。只所以前面认为B—C链和B—D链不可交换，是因为它们不能同时交换，不能同时移去两个同色B。但是，我们总可以只先交换其中之一，先移去一个B吧。由于图8，d1和图8，d2只是左右的不同，实质上应是同一类构形，所以我们就只研究图8，d1一个构形就可以了。

对图8，d1，若先从左上角的顶点1B交换B—D链（如图9，a），得到的是一个DCD型（即双Ｄ夹Ｃ型）的可同时移去两个同色D的Ｋ—构形，问题就得到解决。但要注意的是，下一步同时移去两个同色D的交换中，一定要先从右下角的顶点4D开始进行，后从左上角的顶点1D开始进行。因为若先从左上角的顶点1D开始进行交换，图将又会返回到原来的BAB型的状态，走了回头路。
对图8，d1从1B交换了B—D后，变成了一个可以同时移去两个同色D的K—构形，这是一个必然的结果。因为在交换后的DCD型构形（如图9，a）中，C—A链和C—B链的交叉顶点是6C，5—轮轮沿顶点中用了两次的颜色是D，分别是1D和4D。从6C到4D有一条C—D链，这就正好与我们在前面对图7的分析中所说的形成可同时移去两个同色的条件相同。当从顶点4再交换了D—A后，便生成了从2A到4A的A—C连通链（如图9，b），使得从顶点1D到3B不可能再有连通的D—B链，从而可以再从1D交换D—B，同时移去两个同色D。

对图8，d1（即图10，a），若先从顶点3B交换B—C链（如图10，b），则得到的是一个CDC型（即双C夹D型）的B类H—构形，图中有一条环形的邻角链A—B。该构形从上面的研究中已经知道是可约的了，问题也得到了解决。
对图8，d1从3B交换了B—C后，就会变成一个B类的H—构形，这也是一个必然的结果。因为在交换前的BAB型构形（如图10，a）中，在2A—1B…8A—6C—2A的这个圈中，只有6C一个顶点是着C色的，其他顶点都是着A和B的；而在从3B交换了B—C后，正好使6C变成了6B，形成了一个A—B环形的邻角链，成了一个B类H—构形。
以上解决C类H—构形的方法中，所用的交换方法，目的并不是为了空出颜色，也不是为了进行断链，而是为了构形转化为别的类型，所以我们把这种交换叫做转型交换。
D类H—构形（即图8，e1）：这个图8，e1就是1935年名叫Irving Kittell的一个美国人构造的地图（即无割边的3—正则平面图。当时Irving Kittell与赫渥特一样，只构造了图，但并没有空出颜色给最外面的无限面染上）的对偶图。这是一个没有任何环形链的构形，但又是一个有以A—B链为对称轴的对称构形。

这种对称构形的解决办法是，先要经过两次连续的转型交换，把对称构形转化成象图8，d1和图8，d2那样的非对称的C类H—构形，再用解决C类H—构形的办法去进行解决。由于该构形是对称构形，所以从一个方向进行转型交换就可以了。
在对图８，e1进行了连续两次逆时针方向的转型交换后（如图11），是一个ABA型的H—构形。把图11，b整理变形后，可以看出是一个非对称的C类H—构形（如图12，a）。再用解决C类H—构形的办法，从顶点2A交换A—C链，得到一个CDC型的、有环形的A—B邻角链的B类H—构形（如图12，b）。再用解决B类H—构形的办法去解决。

通过以上的证明，说明各个类型的H—构形都是可约的，也就说明5—轮构形是可约的。极大平面图的四色猜测也就证明是正确的。
以上这些H—构形，当顶点数减少到九点形时，A类H—构形就会变成图7，c；C类H—构形就会变成图7，a和图7，b；d类H—构形就会变成图8，e2；以上这些九点形构形都是可约的K—构形。而只有B类H—构形所变成的九点形构形（如图6）仍是B类H—形。从这里可以看出，赫渥特为了找出坎泊证明中的漏洞是费了功夫的，的确，赫渥特图是一个代表性非常强的图。

（未完，见下贴）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,,,