着色法（交换法）对猜测的证明（修改稿）

雷明85639720

着色法（交换法）对猜测的证明（修改稿）
雷  明
（二○一六年元月二十日）

【摘  要】通过对用四种颜色着色时可能产生的六种色链进行分析，得到在任何5—轮构形中，至少有一条色链是可以进行交换的，这样就能够使任何构形的图都一定可以转化成非H—构形的图，从而可给待着色顶点着上图中已用过的四种颜色之一。四色猜测得证是正确的。
【关键词】四色猜测  平面图  色链  构形  颜色交换  

在对四色猜测的证明过程中，1879年坎泊创造了颜色交换技术。现在大家一直还都在使用着这一技术。由四种颜色构成的色链共六种，设A、B、C、D为四种颜色，则有A—B、A—C、A—D、B—C、B—D和C—D六种色链。
因为任何平面图中总存在着度是小于等于5的顶点，着色时总可以把度小于等于5的顶点放在最后。而度小于等于4的顶点或轮构形的着色，坎泊早已证明了其色数是小于等于4的。现在只有度等于5的顶点为中心的5—轮构形没有被证明是可约的（即是可4—着色的）。因此可以说，现在证明四色猜测的实质，主要就是要证明5—轮构形是否可约的问题。即减少5—轮构形的5个轮沿顶点中占用颜色的总数，空出一种颜色给待着色顶点着上。而要空出颜色，只要轮沿的对角顶点间的色链，在该两对角顶点间是不连通时，对其一支进行交换才能空出颜色来。但交换了连通链则是空不出颜色来的。
本证明就是从分折构形中所有可能的色链能否进行交换来考虑的。如果在某一个图中，六种色链都不可能交换，那么5—轮轮沿顶点中就不可能空出颜色给待着色顶点，四色猜测就不可能证明是正确的。否则，只要有一种色链可以交换，且能给图中的待着色顶点着上四种颜色之一，四色猜测就是正确的。另一方面，在由各色链可能构成的图中，若都能通过交换，证明该构形是可约（可4—着色）的，则四色猜测也就证明是正确的。
1、如果图本身就是一个5—轮或者在5—轮外再不存在对角顶点间的连通链时（如图1），那么该图中就有A—C、A—D、B—C、B—D四条链可以交换，A、B、C、D四种颜色可空出任何一个来给V。

2、如果5—轮构形中至少有一条连通链，或者有两条相交的连通链，但只有一个相交顶点时，这样的情况早在1879年被坎泊已经证明过了，是可以空出颜色给V的，这里我们就不再一个个的进行说明了。
3、如果5—轮构形中存在两条相交的连通链，但相交顶点有两个或两个以上时（如图2）。图中有A—C和A—D两条连通链相交叉，相交于2A和8A。这时一定是不能交换A—C链和A—D链的，因为交换了它也是空不出颜色的。
这种情况比较复杂，我们再细分析如下：
㈠　若能通过交换，能够同时移去两个同色B，把B给V着上，问题也就可以解决了。如图3的三种情况。图3，a无论先交换B—C链还是先交换B—D链，都是可以同时移去两个B的；图3，b要先交换B—C链，后交换B—D链，而图3，c则要先交换B—D链，后交换B—C链才能同时移去两个B，否则，交换的次序错了，则是不能同时移去两个B的。
㈡　若不能同时移去两个同色B，说明了B—C和B—D两链是不能同时交换的，现在剩下的有可能进行交换的链还有A—B和C—D。

①　若C—D链也不能进行交换时，就象赫渥特图那样的图（如图4，这是赫渥特图的简化图），就只有一条A—B链可以进行交换了。因为C—D链是环形链，所以它把A—B链分隔成环内和环外互不相通的两部分，交换其任中一部分A—B链，并不会影响到另一部分A—B链上顶点的颜色。当交换了任一部分的A—B链后，原来连通的A—C和A—D链就都变成了不连通的，起到了“断链”的作用，使得原有的A—C和A—D链都成为可交换的链，为下一步交换空出颜色创造了条件，使问题得到解决。
    ②　换言之，相反的，若A—B链不能进行交换时，就象米勒图那样的图（如图5,图中b、r、y、g分别相当于以上图中的A、B、C、D,b—r链就相当于以上的A—B链），虽然A—B链不能进行交换，但g—y链却可以进行交换。该图中有两条互不相通的b—r链，一条是环形链，一条是直链（道路），交换任一条都不能空出颜色来，也不能为下一步交换空出颜色创造条件。但图中还有两条互不相通的g—y链，也是一条环形链，一条直链，交换了其中任一部分g—y链，却都可以使图变成以上“2”中的虽“有两条相交的连通链，但只有一个相交顶点”的非H—构形的情况，再通过交换是可以空出颜色给V的。

以上的①②两种方法，都是对原有的连通链进行了“断链”，使本来连通的链变成了不链通。所以我们叫它“断链法”。
㈢　再若在不能同时移去两个同色，且b—r和g—y两链都不能交换时，如图6，两个图是一左一右不对称的）和图7（这个图也不对称，当然也可以画出另一个不对称的图来）。这三个图都是雷明先生构造的，叫做L—构形。b—g、b—y、b—r、g—y四种链都不能交换，r—g、r—y两链又不能同时交换，看来就只能交换r—g、r—y两链其中之一了。也就只能用张彧典先生所说的“赫渥特颠倒法”了。
这两个图中没有任何的环形链，b—r和g—y这两条相反色链均只是一条链（道路），谁也没有把谁分隔成两部分，也都不能进行交换。现在我们可以这么想：因为以上的研究都是在r—g和r—y链不能同时交换的情况下进行的，那么既然不能同时交换，我们能不能考虑只交换一条链，而不交换另一条链呢。这当然是可以的。如果连一条链也不能交换，那么我们的图6和图7肯定就不能4—着色，那么四色猜测也就不能证明是正确的了。


现在先看，r—g和r—y链是否可以交换其中之一。r—g链的相反链是b—y链，而在图6和图7中，正好b—y链是连通的，与V构成了一个环，把r—g链分隔成环内环外互不相通的两部分。r—g链既然不连通，当然一定是可以交换的了。虽然单独交换了该链并不能空出颜色给V，但却使5—轮轮沿顶点上的颜色发生了变化。使图变成了一个非L—构形的图，变成以上已说到的可以4—着色的构形中的一种。同样的，当然r—y链也一定是可以单独进行交换的链了。
的确，图6和图7的图，在对有关两个同色r的链进行了一次逆时针的颠倒（即从顶点1交换r—g链）或顺时针的颠倒（即从顶点3交换r—y链）之后，5—轮构形的轮沿顶点中着有两次的颜色r发生了变化，由r变成了g（即构形由原来的双r夹b型变成了双g夹y型）或y（即构形由原来的双r夹b型变成了双y夹g型），图也由L—构形变成了可以同时移去两个同色的非H—构形或类似赫渥特图型的H—构形。这些构形都是可以4—着色的。
这样的交换，只是交换了一条关于两个同色B的链，我们仍按张彧典先生的叫法，叫做“赫渥特颠倒法”，简称“颠倒法”。这里按张先生的次序，把从顶点1进行的B—D链的交换叫做“逆时针赫渥特颠倒”，而把从顶点3进行的B—C链的交换叫做“顺时针赫渥特颠倒”。
4、以上我们研究的都是两条关于两个同色的链不能同时交换的情况，这里强调的是“同时”二字，即只能交换其一，不能两个一前一后紧接着进行交换。但有没有这样的关于两个同色的链一个也不能进行交换的情况呢。也有，但这时的构形就不是H—构形了，而是一个坎泊已经证明过的构形了，如图8。这是雷明先生构造的，也叫L—图或L—构形。图8，a中有一条环形的C—D链，图8，b中有一条环形的A—B链，两个图都有连通且相交叉的B—C和B—D链，但却都没有连通且相交叉的A—C和A—D链。由于A—C和A—D链的不连通，所以两图均可只进行一次A—C或A—D链的交换，就可给待着色顶点着上A、C、D三种颜色之一，如图9。



现在我们已证明了任何一个构形中，六种链中至少有一种是可以交换的，且所能交换的链中均有5—轮轮沿上的顶点，是可以空出颜色给待着色顶点V着上的。同时也证明了在六种链的各种组合情况下，也都是存在有可以交换的链的，也是能够空出颜色给待着色顶点V着上的。这都说明了四色猜测是正确的。四色猜测得到了证明。

雷  明
二○一六年元月二十日于长安

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

修改稿也于二○一六年元月二十四日在《中国博士网》上发表过，网址是：

雷明85639720

,,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，