四色猜测证明方法汇编（二）（共十三种方法，本贴为第6——第8种）

雷明85639720

（接上一贴）

四色猜测证明方法汇编（二）
雷  明
（二○一六年十一月五日）

目     录

1、平面图最小完全同态的顶点数是不大于4的
          ——四色猜测证明方法之一                     （3）
2、任何地图都是可3—边着色的
    ——四色猜测证明方法之二                      （8）
3、平面（球面）上可嵌入完全图的顶点数不大于4
    ——四色猜测证明方法之三                     （15）
4、平面（球面）上是不存在五色地图的
    ——四色猜测证明方法之四                     （18）
5、反证法证明平面上不存在五色地图
    ——四色猜测证明方法之五                     （21）
（以上在贴一）
6、平面图最小完全同态的亏格仍然是0
——四色猜测证明方法之六                     （22）
7、Mycielski—操作与平面图的色数
——四色猜测证明方法之七                     （26）
8、5—轮构形是可约的
——四色猜测证明方法之八                     （31）
（以上在贴二）
9、数学归纳法证明四色猜测
——四色猜测证明方法之九                     （37）
10、哈德维格尔猜测想是正确的
——四色猜测证明方法之十                     （40）
11、用还原法证明四色猜测
——四色猜测证明方法之十一                   （42）
12、用断链法证明四色猜测
——四色猜测证明方法之十二                   （44）
13、赫渥特的地图着色公式是正确的
——四色猜测证明方法之十三                   （46）
（以上在贴三）

平面图的最小完全同态的亏格仍然是0
——四色猜测证明方法之六
雷  明
（二○一六年十一月一日）

在《平面图最小完全同态的顶点数是不大于4的——四色猜测的证明方法之一》一文中虽然已证明了平面图的最小完全同态的顶点数是不会大于4的，但并没有说明这个最小完全同态的亏格与原图的亏格之间的关系。因为最小完全同态都是K4的图，其原图的亏格可能是不同的，有的是0，是平面图；而有的却是1，则是非平面图；有的原图中最大团就是K4，而有的则是K3。所以有必要再研究一下平面图的最小完全同态的亏格问题，并从这一角度去研究一下四色猜测。
1、图的亏格：
研究图的亏格，首先要知道曲面的亏格，因为图是可嵌入曲面上的。所谓嵌入，即是把图画在曲面上后，除了在顶点处有边与边相交叉外，别的地方再没有边与边相交叉的情况存在。曲面的亏格，形象的说，就是把在“球”面上所“焊接”的“环柄”的多少，或者在“棒形饼干”面上所“挖去”的“孔洞”的多少，定义为曲面的亏格。曲面上有几个环柄或孔洞，其亏格就是几。一个图可以嵌入在多个亏格的曲面上，把其中亏格最小的曲面的亏格，就叫做可嵌入到该曲面上的图的亏格。例如K5和K3，3都能嵌入到亏格为1的轮胎面上，而不能嵌入亏格为0的球面（平面。从测地学的观点上看，球面和平面的亏格是相同的，都是0）上，所以K5和K3，3的亏格都是1；而K4虽然能同时嵌入到轮胎面和球面上，但两个曲面的亏格最小的是0，所以K4图的亏格就是0。
2、图的最小完全同态的亏格小于等于原图的亏格在《平面（球面）上可嵌入完全图的顶点数不大于4——四色猜测证明方法之三》一文中已经证明了可嵌入每种亏格曲面都对应有一个顶点数最多的完全图，其顶点数是v≤＜（7＋√（1＋48n））/2＞，这也就是可嵌入该曲面的图的最大密度 。别的可嵌入该曲面的同亏格的图的最大团的顶点数也一定是不大于v≤＜（7＋√（1＋48n））/2＞。这些图同化的最后结果——最小完全同态的顶点数也是不会大于v≤＜（7＋√（1＋48n））/2＞的。虽然图同化时，最小完全同态的顶点有增大的可能，但其增大是不可能大于其可嵌入的曲面上的最大完全图的顶点数的，否则，这个图就不可同嵌入到该亏格的曲面上了。所以说，图的最小完全同态的顶点数一定是小于等于其可嵌入的曲面可嵌入的最大完全图的顶点数的，其亏格也是不大于其原图的亏格的。
例如，一个最大团是K4的图，不大于亏格为0 的平面图的最大完全图的顶点数，虽其色数可以是5，最小完全同态的顶点数是5，但从所画的图中可以看出，这种图总是存在着在顶点以外边与边相交叉情况的，其边数也是大于3v－6的，这个图本身就是不能嵌入亏格为0的平面上的非平面图，其亏格本来就是1，如图1。由于最大团是K2的K3，3的亏格是1，但其最小完全同态的顶点数却仍是2，是一个亏格为0的平面图，如图2；还有最大团是K4的非平面图，其最小完全同也可能仍是K4，也是一个亏格为0的平面图，如图3。



3、平面图的最小完全同态的亏格仍是0
上面已证明了任意图的最小完全同态的亏格是不大于原图的亏格的，那么亏格为0的平面图的最小完全同态的亏格也就一定是不大于0的，最小完全同态仍是平面图。
4、四色猜测的证明
在亏格为0的图中，完全图的顶点数只有1，2，3，4四种，均不大于4。又由于图的色数等于其最小完全同态的顶点数，平面图的最小完全同态的亏格仍是0，所以平面图的色数也就不会大于4。这也就证明了四色猜测是正确的。

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

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


Mycielski—操作与平面图的色数
——四色猜测证明方法之七
雷  明
（二○一六年十月三十一日）

Mycieski（米歇尔斯基）—操作是一种可以保持图的密度不变，即最大团不变，但色数却比操作前增大1的构造图的操作方法。
1、Mycieski（米歇尔斯基）—操作
数学家狄拉克1953年在其论文《k—色图的构造》一文中提出一个问题：对于任意大的一个正整数k，是否存在一个图，不包含三角形但色数是k？这一问题分别在1954年和1955年分别由勃兰克•斯德卡兹和米歇尔斯基独立的作出了回答。米歇尔斯基（Mycielski）给出的由一个不含三角形的k色图Gk构造一个不含三角形的k＋1色图Gk＋1的方法是：设Gk的顶点是u1，u2，……，un,，添加点v1，v2,……，vn和点v0。将vi与ui所有邻点及v0相连，1≤i≤n。如此得到的图就是一个不含三角形的k＋1色图。这里所说的不含三角形的图实际上就是基图Gk的密度是小于3的图。米歇尔斯基的这一构造方法在图论界把它叫做Mycielski—操作，简称M—操作。且这一操作过程是可以递推的，即可以多次进行的。每进行一次M—操作，图的密度并不发生变化，但其色数却增加1。于是，就有了“存在无三角形且色数任意大的图”的说法。实际上，进行M—操作时的基图的密度可以是任意的，不一定都得是密度小于3的图。
我们通过对米歇尔斯基操作的研究认为，M—操作实质上是对一个顶点数为v的连通图G（基图），增加一个星点数u＝v的u—星（注意：u—星有u＋1个顶点，星的密度是2），该星形图的点数u比基图的顶点数多1，即u＝v＋1。然后，把u—星的u个星点顶点ui与图G中对应顶点vi的所有相邻顶点用边连接起来（注意：但ui与vi并不连接），这就是M—操作。使每一个星点顶点ui最多只能与基图中含有vi顶点的最大团Kn中的n－1个顶点相邻，以保证图的密度不变。请注意，星形图的中心顶点u0与基图G中的任何顶点都是不相邻的。
M—操作后所得图的色数只所以比原基图的色数增大1，可以这样理解：① 由于增加的星形图的各个星点顶点均不相邻，所以这些星点顶点是可以同化成一个顶点的，这样，v个星点顶点同化后的这个顶点就与基图中着有各种颜色的顶点都相邻了，这个顶点只有着原基图中所用颜色以外的另一种颜色，使得M—操作后的图的色数比原基图的色数增大了1。而星形图的中心顶点u0又与基图中各顶点均不相邻，给其着以基图中已用过的任一种颜色就可以了。② 若把所增加的星形图中各星点顶点分别着以基图中所对应顶点的颜色，这时这些星点顶点也就用完了基图中已用过的颜色数，星形图的中心顶点也就只能着以基图中已用过的颜色以外的另一种颜色了，使得M—操作后的图的色数比原基图的色数增大了1。
    2、Mycieski—操作与四色猜测的关系
既然M—操作能保持原图的密度不变，其色数可以比原图增大1，那么我们可以对平面图的各种大小的团进行一下M—操作，看其色数增加后是否大于4，且图是否还是平面图。若进行了M—操作后的图的色数不大于4，且图又仍是平面图时，则四色猜测就是正确的；若M—操作后的图的色数大于4，但图仍是平面图时，则猜测就是不正确的。
3、对平面图各种团进行M—操作
平面图中一共有四种团，即K1，K2，K3和K4，各团的色数与其顶点数是相同的。现在一个个地对其进行M—操作，如图1。

    ①  K4团：M—操作后是一个非平面图（图中不但出现了在顶点以外边与边相交叉的情况，且9个顶点，应有3v－6＝21条边，而实际上图中已是22条边了），不是四色猜测研究的对象了。所以含有K4团的平面图的色数一定是其顶点数4≯4；
②　K3团：M—操作后还是一个平面图，色数是4，不大于4，但图中含有4—圈，从图1中可以看出，4—圈在M—操作后却是一个非平面图（图中出现了在顶点以外边与边相交叉的情况），也不是四色猜测测研究的对象了。所以K3团只能进行一次M—操作，色数最大是4≯4。因此，含有K3团的平面图的色数一定是小于等于4的；
③　K2团：M—操作后也是一个平面图的5—圈，色数是3，也不大于4，但对5—圈再进行一次M—操作时，从图1中也可以看出，得到的也是一个非平面图（图中也出现了在顶点以外边与边相交叉的情况），也不再是四色猜测研究的对象了。所以K2团只也能进行一次M—操作，色数最大是3≯4。因此，只含有K2团的平面图的色数也一定是小于4的；
④　K1团：K1团不可进行M—操作，因为K1团的密度本身只是1，而1—星本身的密度却是2，进行了M—操作后，虽然色数也增加了1，但图的密度也由1必然要增大到2，不符合M—操作密度不变的要求。而K1就只是一个孤立的顶点，一种颜色也就够用了。
4、四色猜测是正确的
综上所述，可以看出任何平面图（顶点）着色时，四种颜色一定够用了。这也就证明了四色猜测是正确的。这与用同化理论证明得出的结果一模一样。同化理论中K1团没有不可同化道路，色数只能是1；而这里K1团也不能进行M—操作，色数也只能是1。同化理论中K2团最多只有一条不可同化道路，密度是2的图的色数最大只能是3；而这里K2团也只能进行一次M—操作，密度是2的图的色数最大也只能是3。同化理论中K3团最多也只有一条不可同化道路，密度是3的图的色数最大只能是4；而这里K3团也只能进行一次M—操作，密度是3的图的色数最大也只能是4。同化理论中K4团是不可能有不可同化道路的，密度是4的平面图的色数也只能是4；而这里K4团也是不能进行M—操作的，密度是4的平面图的色数最大也只能是4。都说明了任何平面图的色数都是不大于4的。四色猜测是正确的。

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

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


5—轮构形是可约的
——四色猜测证明方法之八
雷  明
（二○一六年十一月一日）

坎泊已经证明了地图的不可免构形集是由2—轮构形，3—轮构形，4—轮构形和5—轮构形组成的集合：{ 2—轮构形，3—轮构形，4—轮构形，5—轮构形 }，并且于1879年证明了2—轮构形，3—轮构形，4—轮构形以及一部分5—轮构形是可约的，即是可4—着色的。而遗漏了5—轮构形中，在5—轮的对角顶点中含有两条连通链，且两链有两个以上相交顶点的情况。1890年赫渥特构造出了这样的一个具有被坎泊遗漏了的构形的图——赫渥特图，但坎泊与赫渥特都不能对其进行4—着色。可以说，至少在1990年以前——爱好者没有对赫渥特图4—着色以前，是没有人对赫渥特图进行4—着色的。现在我们就仍然使用坎泊所创造的颜色交换技术，证明赫渥特构造的这一类构形是否可约。
1、赫渥特图（构形）的特征
赫渥特图的主要特征是在5—轮的轮沿顶点外，存在着两条有两个相交顶点的A—C和A—D链的图，当然该两连通链是不能进行交换的。赫渥特图中还存在着一条C—D环形链（含有5—轮轮沿上的顶点4和5两个顶点），分A—B链为环内、环外互不连通的两部分。赫渥特类型的构形如图1，a，这里特别要指出的是，该图中顶点6与7是一个单边，这是一个关键的地方。如果这6—7之间不是单边时，则这种有种两条有两个相交顶点的A—C和A—D连通链情况的构形，都是可以同时移去两个同色B给v而成为可约的。正因为6—7是单边，才产生了若从顶点1交换了B—D链后，则形成了从顶点3到顶点5的连通链B—C，使得B—C链再不能进行交换了；若从顶点3交换了B—C链后，又形成了从顶点1到顶点4的连通链B—D，也使得B—D链再不能进行交换了；出现了只能移去一个B，而不能同时移去两个B的情况。
2、赫渥特图的4—着色

现在赫渥特图（图1，a），是不可能同时移去两个同色B的，但可以从两链的任何一个相交顶点8（或1）开始交换A—B链，把连通的A—C和A—D链“断开”，使图变成一个有两条连通的B—C和B—D相交的、但只的一个相交叉顶点8B（或A）的可约构形（两链没有共同的起始顶点），如图1，b。我把这一解决方法叫“断链法”，这里是从两连通链的相交顶点进行断链的（其中一个相交顶点在5—轮的轮沿上）。
3、赫渥特类型的可移去两个同色的构形
如果图中有一条A—B环形链（只含有5—轮轮沿上的顶点2一个顶点），把C—D链分为环内、环外互不连通的两部分时，如图2，a。就是一个可同时移去两个同色B给V着上的赫渥特类型的构形，如图2，b。这里两次对关于B的链的交换是不分先后次序的。
另一种情况是，如果既没有A—B环形链，又没有C—D环形链，1B—8A，4D—6C，5C—7D，3B—8A都只是单边时，如图3。这又是两个可同时移去两个同色B给V的赫渥特类型的构形，但这两个构形两次交换关于B的链的次序是有区别的，即是有先后次序的（图中已写清了），若不按先后次序进行，则是不能同时移去两同色B的。


4、赫渥特类型的敢峰—米勒图的着色
敢峰—米勒图如图4（图4的画法是隐去了待着色顶点V的画法），其中A—B链和C—D链均有环形部分（圈）和直链部分（道路），两部分相同色链被相反的环形色链分隔开来，互不连通。环形的A—B链仍只经过5—轮的轮沿顶点2一个顶点，而环形的C—D链则不经过5—轮的轮沿顶点，而是另一条C—D直链经过5—轮的轮沿顶点4和5两个顶点。该图想通过从两链的相交顶点8（或2）交换A—B链进行断链，是不能达到目的的。我们可以想，只要把连通链能够断开，不一定都得从两链的相交顶点进行，别的顶点也是可以的。所以，从两链的非相交顶点4和5交换C—D链，或者从非相交顶点6和7等顶点交换C—D链，都可以使原来的A—C、A—D连通链断开，而成为可以同时移去两个同色B给V的、仍有两条连通链A—C和A—D，且只有一个共同起始顶点2的构形（没有相交叉的顶点）。这种解决敢峰—米勒图的方法也叫“断链法”。

5、一个特殊的赫渥特类型的构形
在以上的图3中，如果顶点1B—8A，4D—6C，5C—7D，3B—8A间均不是单边，而是一条链，图中又不存在任何环形链时，A—B链和C—D链都是一条直链，情况就比较复杂一点，如图5。
解决这类构形，既不能同时移去两个同色B，也不能用“断边法”使连通的A—C和A—D链断链，那么，就只有先交换一个关于B的链B—D或B—C，使构形由两个同色是B的“双B夹A型”的BAB型的5—轮构形，变成两个同色不是B的别的类型的“双×夹×型”的5—轮构形。
对图5中的两个图，从顶点1进行了B—D链的交换后，都可变成“双D夹C型”的DCD型的5—轮构形，而从顶点3进行了B—C链的交换后，也都可变成“双C夹D型”的CDC型的5—轮构形。变型后的构形，也存在着有没有环形的A—B链或环形的C—D链的问题，可能会成为可同时移去两个同色的构形，也可能会成为需要进行“断链”的赫渥特图或敢峰—米勒图，都可以用与前相同的方法进行解决。若还不能解决时，就再次进行变型，总是可以得解的。

例如在对图5左图从顶点1开始进行了B—D链的交换后，可变成一个“双D夹C型”的DCD型的构形，这个构形是可以同时移去两个同色的D的，但交换关于D 的两条链是有先后次序的；在对图5左图从顶点3开始进行了B—C链的交换后，可变成一个“双C夹D型”的CDC型的构形，这个构形是一个赫渥特型构形，可以用断链法进行解决。因为图5中左、右两个图是对称的，所以右图也就不再多说了。图读者可以自已去画一图。
6、四色猜测的证明
现在，我们已经证明了5—轮构形无论在那一种情况下的构形都是可约的，加上坎泊以前已经证明过的可约构形，地图的不可免集中的各个构形都已是可约的了。这就证明了四色猜测测是正确的。

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

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

（未完，接下一贴切）

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，