平面图不可避免构形的分类和四色猜测的证明

雷明85639720

平面图不可避免构形的分类和四色猜测的证明
雷  明
（二○二二年七月二十二日）

由于图是无穷多的，虽然不可能把所有的平面图都进行4—着色，但却可以证明平面图的不可避免构形都是可约的，即是可4—着色的。这样，四色猜测也就能够得到证明是正确的。
1、平面图的构形：把还有一个顶点未着色的平面图就叫平面图的构形。未着色的顶点叫待着色顶点，与待着色顶点相邻的顶点叫围栏顶点，简称“围栏”。
2、平面图构形分类的原则：多级分类。每一级只分两个非此即彼的类别，以防遗漏。每一级所分的两类，一类是可约的，另一类是暂时不可约的，再去进行下一级的分类。直到所分的两类都是可约的构形为止。
3、一级分类：把构形分为可避免构形与不可避免构形两类。前者待着色顶点的度大于等于6，也有无穷多个；后者待着色顶点的度小于等于5，只有有限的六个（种）。
依据：因为任何平面图中都至少含有一个顶点的度是小于等于5的。因此，对于任意的平面图，总可以把待着色顶点放在度是小于等于5的顶点之上。
无穷多的可避免构形可以不再去研究它，而只研究不可避免的六种构形的解决办法就可以了。这就把一个无穷的问题转化成了一个有穷的问题了。
4、二级分类：把不可避免构形分为可直接给待着色顶点着色的构形和不可直接给待着色顶点着色的构形两类。前者围栏顶点占用的颜色数小于等于3，后者围栏顶点占用的颜色数已经达到了4。
依据：有些构形的待着色顶点的度是小于等于3的，围栏顶点所占用的颜色数只能是小于等于3的；有些构形的待着色顶点的度虽然大于等于4，但围栏顶点所占用的颜色数却有可能是小于等于3的。这些构形围栏顶点所占用的颜色数都小于4，所以待着色顶点都是可以着上图中已用过的四种颜色之一。
可直接给待着色顶点着色的构形，也可以不再去研究了，因为它的待着色顶点已经着上了四种颜色之一；只研究不可直接给待着色顶点着色的构形就可以了。
染色困局构形：这种不可直接给待着色顶点着色的构形就是染色困局构形。因为其待着色顶点似乎是不可能着上图中已用过的四种颜色之一了。但这种构形可通过使用坎泊的颜色交换技术，对某些顶点的颜色进行交换，却是可以给待着色顶点着上四种颜色之一的。这种染色困局构形有时也可叫做发生了颜色冲突的构形。
5、三级分类：把不可直接给待着色顶点着色的构形分成坎泊的可约的K—构形和赫渥特图类的H—构形两类。
依据：前者是坎泊在证明时已经解决了的可约构形。他们都可以经过一次，或者最大两次的坎泊交换，就可从围栏顶点中空出一种颜色来给待着色顶点着上的可约构形（K—构形）。这种交换就叫做可空出颜色的交换；而后者是坎泊证明中所遗漏了的、不能简单的经过一、两次坎泊的可空出颜色的交换空出颜色给待着色顶点的构形。
K—构形也不需要再研究了，因为这些构形坎泊早已证明是可约的了；现在需要研究可约性的就只是H—构形一种了。
H—构形：不能简单的经过一、两次坎泊的可空出颜色的交换就可从围栏顶点中空出颜色给待着色顶点的构形，就是H—构形。
6、四级分类：把H—构形再分成有经过了围栏顶点的环形链的构形和无环形链的构形两类。前者可以用断链法断开双环交叉链，使其转化成可约的K—构形；后者可以用转型法经过不大于40次的交换使构形可约。并且在转型的过程中随时都有可能转化成有环形链的构形的可能，随时都可以改用断链法，以提前结束转型。
依据：因为H—构形中一定含有双环交叉链，也正是因为有了双环交叉链，才使得在移去了一个同色时，又新生成了从另一个同色顶点到其对角顶点的连通链，所以才不能连续的移去两个同色。因此，要解决H—构形的可约性问题，就必须要破坏双环交叉链。
因为在BAB型的H—构形中，有了连通的A—C链和A—D链（即双环交叉链），该两链是不能进行交换的，也是不能空出A、C、D三色之一；该构形又不能连续的交换B—C链和B—D链而空出B来。由A、B、C、D四种颜色所能构成的A—B、A—C、A—D、B—C、B—D、C—D六种色链，现在已有四种都不能交换了，剩下就只有A—B链和C—D链还可以交换。正好这两种链又是一对相反链，是不能相互穿过的。该两种链如果有一条是环形链时，另一条一定是被隔离在环形链的两侧的。交换环形链任一侧的相反链时，都不会影响到环形链另一侧的相反链。这就为断开双环交叉链创造了条件。
如果构形中含有A—B环形链时，交换A—B环内、外的任一条C—D链，都可以使双环交叉的A—C链和A—D链断开，使构形转化成可约的K—构形；同样的，如果构形中含有C—D环形链时，交换C—D环内、外的任一条A—B链，也都可以使双环交叉的A—C链和A—D链断开，构形也就转化成了可约的K—构形了。然后还都可以再用解决K—构形的办法（即可从围栏顶点中空出颜色的坎泊交换法）去解决其可约性的问题。
对于不含有经过围栏顶点的环形链的构形，A—B链和C—D链都只有一条，且也都是直链，也都不能进行交换，也就只能先移去一个同色，使构形转型，再对转型后的构形进行可约性的研究。可以证明，最大的转型次数不会超过40次的，就可以转化成可约构形的。
7、最大转型次数是40次的证明：有这样一个有环形链的H—构形——埃雷拉E—图，该构形是可以通过断链法得到解决的。但这个图如果在进行转型交换时，却是一个无穷周期循环转型的构形，用转型法永远得不到解决。根据原命题的逆否命题与其原命题是“同真同假”的逻辑关系，可以肯定，非E—图的构形一定是有限次转型就可解决问题的构形。E—图转型时，20次是一个周期。E—图当转型次数达到20次后，这时，是不能够确定其是否是周期转型的，还必须等到转型次数达到第二个20次后，才能确定该图是产生了周期循环转型的构形。E—图是这样的，如果有别的图也是周期循环转型的构形时，也应该是这样的。但我们这里所研究的构形已经知其是有限次转型的构形，是不可能再出现第二个循环周期的。所以无环形链的构形的最大转型次数只能是E—图构形转型周期的两倍，即40次。的确，我们也已经构造过转型次数大于20，但又小于40的H—构形，说明了这种构形的确是存在的。

现在，对平面图不可避免构形经过以上的四级分类，各级所分的两类都已经是可4—着色的可约构形了，所以四色猜测也证明是正确的了。
该文实现了我多年的梦想——用最短的语言，最少的文字，不画图，不着色对四色猜测进行证明的想法。该文大约只有三千字。
   
雷  明
二○二二年七月二十二日于长安

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，