四色猜测是可以手工证明的

雷明85639720

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

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

目前研究四色问题，主要只应该研究H—构形是否可约就行了。研究H—构形的可约性问题，首先要知道H—构形有多少种，它的不可免集是什么，有多大。并且要明确什么是H—构形，才能构造出不同结构的H—构形来。
H—构形的定义：H—构形应该是既含有两条相交叉的连通链（两链有共同的起始顶点）的构形，又不能同时移去两个同色的构形。
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图那一种环形链都没有；e图是两种环形链都有。除了这些外，再没有别的环形链分布模式了。
   2、2  这三个图中的A—C链和A—D链是连通链，都与待着色顶点一起构成了一个环或圈，其链的本身是不可能构成环形链的；由于A—C链和A—D链的连通性，则其相反的B—D链和B—C链就不可能再是连通的了。四种颜色所能构成的六种链中，上述这四种链已经固定，不能变动，那就只有变动另外的两种，即A—B和C—D链了。这就是我们在1中所分析的内容。

2、3  以上图1和图2中的构形，当顶点数减少到九点形图时，分别就变成了与图3和图4中所对应的各图。图1和图2中的e图也就变成了图3和图4中的a图2、4  在图1和图2的a图，b图，c图三个图中，除了5—轮的5条轮沿边和C—7D—6C—D三条边只能是单边外，其他的任何边都可以看成又是由其两个端顶点的颜色所构成的色链，即其中还可以含有别的顶点。如果在C—7D—6C—D这三条边中还有别的顶点时，图就变成了可以同时移去两个同色的K—构形，而不再是H—构形了。关于这一点，读者可以自已画图试一试，看是不是可以同时移去两个同色B。和b图。图3和图4中的这四个图除了b图仍是H—构形外，其他的三图都已变成了可以同时移去两个同色B的K—构形了。

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  对于a图的构形，由于有A—B链是环形的，所以它把C—D链分成了环内、环外互不连通的两部分。又由于环形的A—B链交换后不起任何作用，所以，现在就只有一种C—D链是可以交换的了。当交换了被环形链A—B所隔开的任一部分C—D链后，都可使连通的A—C链和A—D链断开，使图变成为坎泊的K—构形而可约（如图5，以后如何交换，使得待着色顶点周围的顶点所占用的颜色总数由四种减少到三种，就属于坎泊的证明范围了，也就不再画图了）；

3、2  对于b图的构形，由于有C—D链是环形的，所以它也把A—B链分成了环内、环外互不连通的两部分。也是由于环形的C—D链不可交换的原因，所以，现在也只有一种A—B链是可以交换的了。当交换了被环形链C—D所隔开的任一部分A—B链后，也都可使连通的A—C链和A—D链断开，使图变成为坎泊的K—构形而可约（如图6，以后的交换同样也属于坎泊的证明范围了）。赫渥特图的4—着色就是用这种方法解决的。把具有这种特点的构形，我们叫它类赫渥特图型的H—构形；
3、3、 以上3、1和3、2中的交换办法，我叫他“断链交换”法，是坎泊所创造的颜色交换技术的又一种应用。而坎泊在证明中只用了他创造的颜色交换技术的一种应用，即“空出颜色”的交换的应用。

3、4  对于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  对于c图和d图，由于其中没有环形链，而且A—B链和C—D链均是直链（即是一条道路），且只有一条，即就是交换了，也不起任何作用，图仍不会变成K—构形。而B—C链和B—D链又不能同时交换，不能同时移去两个同色B。没办法，我们就只好先交换一种链，先移去一个B，使图由123—BAB型转化成为451—DCD型或345—CDC型。然后，再视转型后的图的类型再进行研究。

3、6  对于c图和d图转型交换的结果，从不同的两种方向交换看，不同的交换方向，有不同的交换结果：一是转化成了可以同时移去两个同色的K—构形（如图7）；另一是转化成了类似图2中b图的有一条环形链的类赫渥特图型的H—构形（如图8，该构形是可以通过断链交换转化成坎泊的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图着色时，要注意的是两种构形断链时所用以交换的链是不同的。如在a图中有环形的A—B链时，交换的是C—D链，而在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边。以致从1B交换了B—D后，生成了从顶点8到顶点1的A—D边，使得从3B到5C不可能再有连通的B—C 链；而从3B交换了B—C后，则生成了从顶点8到顶点3的A—C边，也使得从1B到4D不可能再有连通的B—D链；从而可以同时移去两个同色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后，生成了从6C到4A的C—A链（如图9，b），使得从顶点1D到3B不可能再有连通的D—B链，从而可以移去两个同色D。这就证明了无环形链的H—构形是一定可以转化成为可以同时移去两个同色的K—构形的。对图2，d的构形从3B施行了一次顺时针转型交换后，得到的345—CDC型的5—轮构形，也有同样的结果。


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），当对c图从顶点3交换B—C（或对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—构形的不可免集已证明是完备的，其中的各个不可免构形也证明都是可约的；那么再加上以前坎泊在一八七九年所证明了的结果，说明了平面图的不可免构形都是可约的。这就证明了平面图的四色猜测是正确的。由于给地图的面的着色就是给极大的平面图的顶点着色，所以也就证明了地图的四色猜测是正确的。所以说四色猜测是正确的。

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

   

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，

雷明85639720

,,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，

雷明85639720

,,,,,,,,