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

雷明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—轮轮沿顶点中就不可能空出颜色给待着色顶点，四色猜测就不可能证明是正确的。
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两链都不能交换时，就象张彧典先生的第八构形（即Z—构形，如图6，这是张先生第八构形的简化图，两个图是一左一右不对称的）和雷明先生在张先生Z—构形基础上构造的图（即Z—L构形，如图7，这个图也是不对称的，当然也可以画出另一个不对称的图来），这时就只能用张彧典先生所说的“赫渥特颠倒法”了。
这两个图中没有任何的环形链，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—轮轮沿顶点上的颜色发生了变化。同样的原因，r—y链也一定是可以进行交换的链了。
的确，通过交换一条关于两个同色r的链r—y后，我们可以发现，5—轮构形的轮沿顶点中着有两次的颜色r发生了变化，由r变成了g（即构形由双r夹b型变成双g夹y型），得到的仍是一个5—轮构形。仍然存在着本文以上所说的各种情况，这些情况都是可以用四种颜色解决问题的。若这一交换后得到的图仍是一个如图6和图7的构形，就继续进行这样的关于两个同色的色链之一的交换，总是可以变成以上可以用四种颜色解决问题的某一种情况的。四色问题就得到了证明是正确的。
这样的交换，只是交换了一条关于两个同色B的链，我们仍按张彧典先生的叫法，叫做“赫渥特颠倒法”，简称“颠倒法”。这里按张先生的次序，把从顶点1进行的B—D链的交换叫做“逆时针赫渥特颠倒”，而把从顶点3进行的B—C链的交换叫做“顺时针赫渥特颠倒”。由于这两种颠倒是互逆的，所以在具体操作时，在确定了“颠倒”的方向后，下一步的“颠倒”仍需要坚持原确定的“颠倒”方向。否则就会陷入无限循环的陷阱之中。另外，在进行了某一步的“颠倒”之后，只要不再是图6和图7类型的构形时，就应及时的使问题得到解决，不要再进行“颠倒”了。否则不但一是耽误时间，而且二是会因为“颠倒”的次数多了，就多增加了出错的机会，使本来能够4—着色的图，误认为是不可能4—着色的。如赫渥特和米勒那样，都把本来可以4—着色的赫渥特图和米勒图都误判成了不可4—着色的图，造成了长达跨世纪的错误。
雷  明
二○一六年元月二十日于长安

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

雷明85639720

，，，，，，，，