《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（二）

雷明85639720

（接上贴）

三十多年研究四色问题的总结：《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（二）

四色猜测是可以手工证明的
雷  明
（二○一七年元月二十六日）

【摘  要】从分析构形的结构入手，构造了完备的H—构形的不可免集，也证明了该集中的所有不可免的H—构形都可以转化成坎泊的K—构形，即都是可约的。加上坎泊一八七九年早已证明了的可约的不可免构形，平面图的所有不可免构形都是可约的了，这就证明了四色猜测是正确的。
【关键词】四色猜测  四色问题  平面图  构形  不可免构形  不可免构形集   链  交换  可约构形

目前研究四色问题，主要只应该研究H—构形是否可约就行了。研究H—构形的可约性问题，首先要知道H—构形有多少种，它的不可免集是什么，有多大。并且要明确什么是H—构形，才能构造出不同结构的H—构形来。
H—构形的定义：H—构形应该是既含有两条相交叉的连通链（两链有共同的起始顶点）的构形，又不能同时移去两个同色的构形。H构形只是坎泊的不可免构形中的5—轮构形中的一种，也就是坎泊证明中所漏掉的、还没有证明是否可约的那一种构形。
1、 H—构形的不可免集
根据H—构形的定义及其特征，我构造出了如下五种不同结构类型的H—构形。在这里，我用了两种不同形式的画图方法：一是英国的米勒所使用的待着色顶点是隐形的画法（如图1）；二是我国的张彧典先生所使用的待着色顶点是显形的画法（如图2）（当然我还有我自已的画法，这里就省略不画了）。这两个H—构形的不可免集实质上是同一个集合，只是图的画法不同而已。从该集合中看，好象是有五个元素（构形），实际上却只有三个不可免构形。

以上的H—构形的不可免集中，明明画了五个构形，为什么又说实际上只有三个呢。这是因为a图中有一条环形的A—B链；b图中有一条环形的C—D链；c图和d图中都既没有环形的A—B 链，也没有环形的C—D链，而且两图的结构正好是左右相反的，实际上应该是同一类构形；e图则是A—B环形链和C—D环形链都有的构形，这就是敢峰—米勒图。e图既有a图的特征，又有b图的特征，既可归入a类构形中，也可归入b类构形中，因此，它不是一类单独的构形。这样，集合中的构形数目，就只有a图、b图、c图的三类构形了。这就是我所构造的H—构形的不可免集，其中只有三个元素，即三个构形。

2、 H—构形不可免集完备性的证明
2、1  这三个构形从有没有环形链的角度来分：a图、b图、e图皆有环形链；c图、d图皆没有环形链。从环形链的条数角度来分：c图、d图都是0条；a图、b图都是1条；e图是大于一条的代表。从环形链的种类角度来分：a图只有A—B一种环形链；b图只有C—D一种环形链；c图、d图是A—B和C—D两种环形链，那一种都没有的构形；e图是A—B和C—D两种环形链，那一种都有的构形。除了从这些角度分析外，就再没有别的种类的环形链分布模式了。

2、2  这三个构形中的A—C链和A—D链都是连通链，都与待着色顶点一起构成了一个环或圈（该连通链的本身是不能成为环或圈的）；由于A—C链和A—D链的连通性，则与其相反的B—D链和B—C链就不可能再是连通的了。四种颜色所能构成的A—B、A—C、A—B、B—C、B—D和C—D六种链中，上述这四种链已经固定，不能变动，那就只有变动另外的两种，即A—B链和C—D链了。
2、3  以上图1和图2中的构形，当顶点数减少到九点形图时，分别就变成了图3和图4中所对应的各图。图1和图2中的e图也就变成了图3和图4中的a图和b图。图3和图4中的这四个图除了b图仍是H—构形外，其他的三个图都已变成了可以同时移去两个同色B的K—构形了。

2、4  在图1和图2的构形中，除了5—轮的5条轮沿边、轮幅边和边7D—6C只能是单边外，其他的任何边又都可以看成是由其两个端点顶点的颜色所构成的色链，即其中还可以含有别的顶点。如果在7D—6C边中还有别的顶点时，图就变成了可以同时移去两个同色B的K—构形，而不再是H—构形了。关于这一点，读者可以自已画图试一试，看是不是可以同时移去两个同色B。
2、5  到此，就证明了再也没有别的构形是H—构形了（四种颜色所能构成的六种色链中，四种已固定，不能再变动，可以变动的只有两种，这两种链的各种情况都已经考虑到了），所以说，这就证明了我们上面的图1和图2的H—构形的不可免集是完备的。   
3、 不可免的H—构形可约性的证明
H—构形之所以与K—构形不同，主要是由于其中有A—C和A—D两条交叉的连通链而引起的，A—C链和A—D链都是不能交换的。同时，也不能同时移去两个同色B，所以说B—C链和B—D链也是不能交换的。因此，在解决这一类图的着色问题时，我们首先想到的就是能不能把连通的A—C链和A—D链断开，使其变成坎泊的K—构形。只要图变成了K—构形，当然也就可约了。

3、1  对于图2，a的构形，由于有A—B链是环形的，所以它把C—D链分成了环内、环外互不连通的两部分。又由于环形的A—B链交换后不起任何作用，所以，现在就只有一种C—D链是可以交换的了。当交换了被环形链A—B所隔开的任一部分C—D链后，都可使连通的A—C链和A—D链断开。使图变成为不含有连通的A—C和A—D交叉链，又可以同时移去两个同色B的坎泊K—构形而可约（如图5，以后如何交换，就得按K—构形的“空出颜色”的交换，只要使待着色顶点周围的顶点所占用的颜色总数由四种减少到三种就可以了。这就属于坎泊的证明范围了，也就不再画图了）。
3、2  对于图2，b的构形，由于有C—D链是环形的，所以它也把A—B链分成了环内、环外互不连通的两部分。也是由于环形的C—D链不可交换的原因，所以，现在也只有一种A—B链是可以交换的了。当交换了被环形链C—D所隔开的任一部分A—B链后，也都可使连通的A—C链和A—D链断开。使图变成为不含有连通的A—C和A—D交叉链，但又不可以同时移去两个同色B的坎泊K—构形而可约（如图6，以后的交换同样也属于坎泊的证明范围了。如果我们不画出构形最个面的8A到5C和8A到4D的两条边，交换A—B链后，构形就变成了既没有连通的A—C和A—D交叉链，又可以同时移去两个同色B的坎泊K—构形了）。赫渥特图的4—着色就是用这种方法解决的。把具有这种特点的构形，我们叫它类赫渥特图型的H—构形。

3、3、 以上3、1和3、2中的交换办法，我叫它“断链交换”法，是坎泊所创造的颜色交换技术的又一种应用。而坎泊在证明中只用了他所创造的颜色交换技术的一种应用，即“空出颜色”的交换。
3、4  对于图2，e的构形，由于该图既有环形的A—B链，它把C—D链分成了环内、环外互不连通的两部分，交换其中任一部分C—D链，都可使连通的A—C链和A—D链断开，成为坎泊的K—构形而可约；该图又有环形的C—D链，它又把A—B链分成了环内、环外互不连通的两部分，交换其中任一部分A—B链，也都可使连通的A—C链和A—D链断开，成为坎泊的K—构形而可约。敢峰—米勒图的4—着色用这两种办法都是可以解决的；
3、5  对于图2的c图和d图，由于其中没有环形链，而且A—B链和C—D链均是直链（即是一条道路），且只有一条，即就是交换了，也不起任何作用，图仍不会变成K—构形。而B—C链和B—D链又不能同时交换，不能同时移去两个同色B。没办法，我们就只好先交换B—C链和B—D链中的一种，先移去一个B，使图由123—BAB型转化成为451—DCD型或345—CDC型。然后，再视转型后的图的类型再进行研究。

3、6  对于图2，c和图2，d转型交换的结果，从不同的两种方向交换看，不同的交换方向，有不同的交换结果：一是转化成了可以同时移去两个同色C（或D）的K—构形（如图7，图中仍有两条连通的交叉链D（或C）—A和D（或C）—B）；另一是转化成了类似图2中b图的有一条环形链的类赫渥特图型的H—构形（如图8，b。该构形是可以通过断链交换转化成坎泊的K—构形的，如上3、2中所述）。转型交换后，所转化成的两种构形都是可约的。

3、7  这里所说的交换，具有转换构形类型的作用，所以我叫它“转型交换”法，这又是坎泊的颜色交换技术的第三种应用。
4、 有环形链的H—构形一定可以通过“断链”交换转化成K—构形的证明
4、1  有A—B环形链的断链交换可转化成K—构形的证明：
因为在A—C链和A—D链中，至少有6C与7D和4D与5C两对顶点是直接相邻的两个顶点（如果没有这两对顶点的直接相邻，图就不可能再是H—构形了），所以，无论A—B环形链是从哪个地方穿过A—C链和A—D链的，也无论是只穿过一条还是两条都穿过，A—B环形链的某一侧至少是存在着这样的两对顶点之一对的。这就保证了无论从其中的哪一对顶点进行C—D链的交换时，都可以使A—C链和A—D链的一条或两条断开，使构形转化成K—构形。敢峰—米勒图就是这样着色的。
4、2  有C—D环形链的断链交换可转化成K—构形证明：
因为在A—C链和A—D链中，至少有顶点2A和顶点8A是两条链的公共顶点（如果没有这两个公共顶点，图也就不可能再是H—构形了），所以，无论C—D环形链是从哪个地方穿过A—C链和A—D链的，也无论是只穿过一条还是两条都穿过，C—D环形链的某一侧至少也是存在着这样的两个公共顶点之一的。这就保证了无论从其中的哪一个公共顶点进行A—B链的交换时，也都可以使A—C链和A—D链的一条或两条断开，使构形转化成K—构形。赫渥特图就是这样着色的，敢峰—米勒图也可以这样来着色。
4、 3  用以上的两种断链方法对图1和图2的a图以及图1和图2的b图着色时，要注意的是两种构形断链时所用以交换的链是不同的。如在图2，a中有环形的A—B链时，交换的是C—D链，而在图2，b中有环形的C—D链时，交换的则是A—B链。赫渥特图中只有环形的C—D链，所以其只有一种断链的方法，只能任意交换环形的C—D链两侧的A—B链，使图变成K—构形；而敢峰—米勒图中既有环形的A—B链，又有环形的C—D链，所以其不但可以交换环形的A—B链两侧的C—D链，也可以交换环形的C—D链两侧的A—B 链，都可以使图变成K—构形而可约。
4、4  到此，就证明了有环形链的H—构形一定是能够转化成为坎泊的K—构形的。
5、 无环形链的H—构形也一定可以通过“转型”交换转化成K—构形的证明
5、 1  无环型链的H—构形构形可以转化成可以同时移去两个同色的K—构形的证明：
5、1、1  从图4中可以看出，只所以图4，a、图4，c和图4，d可以同时移去两个同色B，是因为两个同色顶点1B和3B中至少有一个B色顶点到A—C链和A—D链两链的交叉顶点8A有一条连通的B—A边（见图4中的a、c、d图）。以致从1B交换了B—D后，生成了从顶点8A到顶点1D的A—D边，使得从3B到5C不可能再有连通的B—C 链；而从3B交换了B—C后，则生成了从顶点8A到顶点3C的A—C边，也使得从1B到4D不可能再有连通的B—D链；从而可以同时移去两个同色B。读者可以对图4进行交换，试试看是否可以同时移去两个同色B。

5、1、2、 现在看看图1和图2中的无环形链的H—构形在施行了一次转型交换后，是不是与图4，a有同样的结果呢。对图2，c的构形从1B施行了一次逆时针转型交换后得到图9，a，是一个451—DCD型的5—轮构形。图9，a中C—A链和C—B链的交叉顶点是6C（即图中加大的顶点），5—轮轮沿顶点中用了两次的颜色是D，从6C到4D有一条C—D链（即图中加粗的边链）；当从顶点4交换了D—A后，生成了从2A到4A的A—C连通链（如图9，b中加粗的边链），使得从顶点1D到3B不可能再有连通的D—B链，从而可以移去两个同色D。这就证明了无环形链的H—构形是一定可以转化成为可以同时移去两个同色D的K—构形的。对图2，d的构形从3B施行了一次顺时针转型交换后，得到的345—CDC型的5—轮构形，也有同样的结果，也是可以同时移去两个同色C的K—构形。
5、2  无环形链的H—构形可以转化成类赫渥特图型的H—构形，再转化成坎泊的K—构形的证明：

在图1和图2的c图（或d图）的构形中，有通过顶点2A—1B……8A—6C—2A（或2A—3B……8A—7D—2A）的缺口是6C（或7D）的A—B圈（如图10，a中加粗的边链），当对图2，c从顶点3交换B—C（或对图2，d从顶点1交换B—D）时，顶点6C变成了6B（或顶点7D则变成了7B），就形成了一条完整的环形的A—B链（如图10，b中加粗的环形链），把C—D链分成了环内、环外互不连通的两部分，构形具有了图1和图2的b图的特点了。是一个类赫渥特图型的H—构形，一定是可以转化为K—构形的。
5、3  到此，就证明了无环形链的H—构形一定是能转化成为坎泊的K—构形的。
6、四色猜测的证明
以上的H—构形的不可免集已证明是完备的，其中的各个不可免构形也证明都是可约的；那么再加上以前坎泊在一八七九年所证明了的结果，说明了平面图的不可免构形都是可约的。这就证明了平面图的四色猜测是正确的。由于给地图的面的着色就是给其对偶图——极大平面图的顶点着色，所以也就证明了地图的四色猜测是正确的。又因为极大平面图经去顶或减边后，所得到的任意平面图的色数只会减少而不会增加，所以，这也就证明了任意平面图的四色猜测是正确的。四色猜测得到了证明是正确的。

用给构形中的待着色顶点着上四种颜色之一，来证明四色猜测的方法，实际上也就是数学归纳法。待着色顶点以外的n个顶点已经是可4—着色的，相当于归纳法中的k，加上待着色顶点后，就是n＋1个顶点了，也就相当于归纳法中的k＋1，这n＋1个顶点的构形能够4—着色，那么任意多顶点的构形也就能进行4—着色了。


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

作者：雷明，金堆城钼业公司退休职工，高级工程师，退休前任钼业公司教育处处长
注：此文已于二○一七年元月二十五日以《从构形结构角度研究H—构形的不可免集及其不可免构形的可约性》的题目曾在《中国博士网》上发表过，网址是：，这次修改后题目改成了《四色猜测是可以手工证明的》。修改后的论文也于二○一七年元月二十八日（春节）在《中国博士网》上发表过，网址是：

（未完，接下贴）

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

。。。。

雷明85639720

，，，，

雷明85639720

tnopo92朋友：
“厉害！强~~~~没的说了！”是什么意思呢？

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，