极大图生成法和不可免构形法分两步证明四色猜测

雷明85639720

极大图生成法和不可免构形法分两步证明四色猜测
雷  明
（二○二○年四月三日）
（在这里我发不上图，请到＜中国下月士网＞中去看）

四色猜测由给地图的染色而提出，对四色猜测的证明还得从地图形始。由于地图本身就是3—正则的平面图，即地图的每一个顶点都连有3条边，其对偶图则是一个各面都是三边形的极大平面图。给地图的面上的染色就相当于给其对偶图的顶点的着色。所以证明四色猜测还得从地图的对偶图——极大平面图开始。只要极大平面图的四色猜测证明是正确的，则地图四色猜测与任意平面图的四色猜测也就都是正确的。这是因为极大平面图经去顶和减边后所得到的任意平面图的色数只会减少而不会再增加。
第一步，用极大图生成法证明任意极大图都是可4—着色的：
面数最少的地图是海地岛的地图，其上有海地和多米尼加两个国家和“海洋国”，共有三个面。其对偶图就是只有三个顶点的极大平面图，这也是最小的极大图。最小的极大平面图就是K3图。用“增加顶点和边”的办法从K3图可生成任意顶点数的、且各顶点的度是任意大的极大平面图。这些极大平面图一定都是可4—着色的。证明如下：
任意极大平面图的生成过程，是从顶点数是3的最小极大平面图K3开始的，因为K3图只有3个顶点，所以三种颜色就够用了。
1、若在K3图的一个面内增加一个顶点，得到的是一个K4图（如图1），也是一个3—度顶点的3—轮构形，仍是极大图，增加的顶点还有第四种颜色可着；若在K3图的一条边上增加一个顶点，再增加边，以保持图仍是一个极大平面图，得到的是一个2—度顶点的2—轮构形（如图2），也仍是极大图，增加的顶点至少还有两种颜色可着。图3也是在K3图的一条边上增加了一个顶点，其度是4，看上去似乎不是极大图，但稍加拓扑变形以后，就能看出图3与图2实际上是同一回事（如图4和图５。图3，图4和图5三个图实际上是同一个图）,只是其只剩下一种颜色可着了。

2、以后再在图1（K4图，3—轮）和图2（2—轮）的基础上，在其面内或边上增加顶点，仍要保持图是极大平面图时，所增加的顶点的度都不会大于4。
（1）若是在一个面内增加顶点时，该顶点的度一定是3（如图6），共增边了三条边，该顶点至少还有一种与该面的三个顶点不同的第四种颜色可着；
（2）若增加的顶点不在面内，而是在一条边上，要使图保持仍是极大平面图时，还得要再增加两条新边，共计也是增加了三条边。因为增加的顶点是在一条边上，就已经把该边分成了两条。增加的这个顶点一定是位于一个4—轮构形的中心顶点上（如图7和图8），该顶点的度都是4。坎泊早在1879年就已证明了任何4—度顶点的构形都是可4—着色的，这里不再重复；

（3）若增加的顶点在一个2—度顶点的一条边上，得到的也是一个2—度顶点的2—轮构形（如图9），也仍是极大图，增加的顶点至少也还有两种颜色可着。图10也是在2—度顶点的一条边上增加了一个顶点，与图3有些类似，看上去似乎不是极大图，实际上仍是极大图，增加的顶点的度也是４，也还有一种颜色可着了（如图11）。可以看出图10与图9实际上也是同一回事。
就这样一直不停的把图的顶点增加下去，就可得到顶点数是任意多的、且各顶点的度也是任意大的任意极大平面图，其所用的颜色数总是不会超过4的。这就证明了任何极大的平面图都一定是可4—着色的。证毕。
第二步，用不可免构形可约法检验纯理论证明的结论是正确的：
因为任何平面图中一定存在至少一个顶点的度是小于等于5的，所经我们在对任何极大平面图着色时，一定可以把最后一个待着色的顶点放在度小于等于5的顶点上。这就是平面图的不可免构形。
1、当构形的待着色顶点的度是小于等于3，或者与待着色顶点直接相邻的围栏顶点所占用的颜色数小于等于3时，待着色顶点至少还是有一种颜色可着的。
2、当构形是围栏顶点已占用完了四种颜色的K—构形时，坎泊早在1879年已证明这类构形都是可约的，这里也不再重复了。
3、当构形是围栏顶点已占用完了四种颜色的、具有双环交叉链的H—构形时，对于各种不同的H—构形，各有不同的处理方法：
（1）当构形中含有经过围栏顶点的环形链时，用“断链交换法”，即交换环形链内、外的任一条与环形链呈相反链的色链，即可使双环交叉链断开，图转化为K—构形而可约。如图12，a和图13，a中分别含有环形的A—B链和C—D链，在环内分别交换了与其相反的C—D链和A—B链后，就都转化为可约的无双环交叉链的K—构形了（如图12，b和图13，b）。如果图中既含有环形的A—B链，又含有环形的C—D链（如图14），则按含那一种环形链的方法交换，都可以使图转化成K—构形。
（2）当构形中不含有经过围栏顶点的环形链时（如图15），则有多种交换方法都能使其转化为K—构形：

ａ、改变某一个顶点的颜色（如图中的加大顶点），使图转化为有环形链的构形。如图16，a和图17，a中分别把加大的顶点B和D分别改成C和B，就都可以转化为有环形链的构形了（如图16，b和图17，b）。
ｂ、从围栏顶点的某一个同色顶点B交换与其对角构成的色链（转型交换一次），也可使图转化为另一类型的有环形链的构形（如图18）。原来的图18，a是BAB型的，构形的峰点是A色，而转型后的图18，b却是CDC型的，构形的峰点是D色。

ｃ、还可以通过有限次连续的“转型交换法”，使图变成交换了一个同色顶点后，并不生成从另一个同色顶点到其对角顶点的连通链的K—构形。如图19，转型两次后，图就不再生成从另一个同色顶点到其对角顶点的连通链的构形了。再交换一次就可空出两个同色D或B给待着色顶点（如图19，c和图19，d）。如果在转型过程中，人为的构造从另一个同色顶点到其对角顶点的连通链时，最多也是在第六次转型后就不可能再构造出从别一个同色顶点到其对角顶点的连通链了。

（3）以上的各种H—构形，不但单独的作为一个图是可4—着色的，而且因为它们最外面的无限面都是三边形面，把它们嵌入任何一个极大图的一个面中时，也是可以用同样的方法进行可4—着色的。这就从着色的实践上进一步验证了从纯理论的证明中得出的“四色猜测是正确的”结论是正确的。

（4）以上的验证用的是雷明对H—构形的分类和解决方法，若用张彧典先生对H—构形分类和解决办法验证时，也可以得到同样的结果。张先生把H—构形分为E—图类构形和非E—图类构形：当图是E—图类构形时，可用“Z—换色程序（即是断链交换法）”，图就变成可约的K—构形；若是非E—图类构形时，可用“H—换色程序（也即是转型交换法）”，图也一定可以在有限次的换色内变成K—构形。此检验方法可，可见张彧典行生的有关文章。
两步走的关键是第一步的纯理论证明，有了这一证明才可以肯定后面检验时的连续转型交换的次数一定是有限的。否则，就不能肯定转型交换的有限性，也是无法证明任何极大图都是可4—着色的。

雷  明
二○二○年四月三日于长安

注：此文于二○二○年四月三日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，，，，，

雷明85639720

,,,,,,,,,,

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，