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

雷明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）


数学归纳法证明四色猜测
——四色猜测证明方法之九
雷  明
（二○一六年十一月三日）

用v表示图的顶点数，用e是图的边数，用f是图的面数，用γ表示图的色数。
当v＝1时，一种颜色就够用了，γ＝1＜4；
当v＝2时，两种颜色也就够用了，γ＝2＜4；
当v＝3时，边数最多时是K3图，是一个极大图，也是一个完全图，两两顶点均相邻，必须用三种颜色着色，γ＝3＜4；

当v＝4时，新增加的这第4个顶点，只有位于上面的K3图的一个面内时，最多可以增加3条边，使K3成为一个极大图K4（如图1左图），也是一个完全图，两两顶点也均相邻，着色时四种颜色也就够用了，γ＝4≯4；
当v＝5时，新增加的顶点，可以在图中的一个面内，也可以在图的一条边上（如图1），只要图不变成非平面图的情况下，尽可能多的使该顶点与图中的其他顶点相邻，最后都可以成为一个极大图：
若该顶点处在图的一个面中（如图1的左图）时，它只能与三个顶点相邻，它还有除三个顶点所着颜色以外的第四种颜色可着；
若该顶点处在图的一条边上（如图1的右图）时，它也只能与四个顶点相邻，按照坎泊1879的证明，这个顶点一定是能着上四种颜色之一的。这就证明了v＝5时的极大图也是可4—着色的，其色数γ＝4≯4。
    从图1中还可以看出，不管增加的点是增加在何处，图中都是因增加了1个顶点而增加了3条边和两个面。若再在图中增加顶点，只要图不变成非平面图，所得到的图一定是极大图，就一定都是可4—着色的，色数都是γ＝4≯4；
当然v＝k时的极大图，当然也是可4—着色的，色数仍是γ＝4≯4。
已知在极大图中都有e＝3v－6和f＝2v－4的关系，所以这里也应有e＝3k－6和f＝2k－4的关系；当v＝k＋1时，按上面的证明和分折，所增加的这一个顶点不但是可以着上图中已用过的四种颜色之一的，而且图中也因增加了这一个顶点而增加了三条边和两个面，使得图的边数和面数分别变成了e＋3和f＋2。代入上两式得：e＋3＝3（k＋1）－6和f＋2＝2（k＋1）－4，化简后仍有e＝3k－6和f＝2k－4的关系，图仍是一个极大的平面图。
到此就证明了任何极大图都是可4—着色的。因为在相同顶点数的平面图中，极大图的边数是最多的，所以边数比极大图少的任意平面图的色数也一定是不会大于4的。这也就证明了四色猜测是正确的。

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

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


哈德维格尔猜想是正确的
——四色猜测证明方法之十
雷  明
（二○一六年十一月三日）

1943年的哈德维格尔猜想是：“若图G是n色的，则G可以收缩为一个完全图Kn。”这里的“收缩”一词与我所用的“同化”一词是同一个概念，都是把两个不相邻的顶点凝结在一起的过程。这个完全图Kn，就是色数是n图同化最终的最小完全同态Kn的顶点数n。这个猜想很容易证明：因为相同颜色的顶点一定是不相邻的，他们属一个顶独立集内的顶点，是可以同化为一个顶点的。图同化的结果——完全图Kn——中一定有n个顶点；Kn中n个顶点均相邻，是因为这n个顶点中的每一个顶点，都代表的是若干个在原图中不相邻的、但又是着有相同颜色的顶点，且其中至少有一个顶点是与这个完全图Kn中的其他顶点是相邻的。
已知一个图中只要含有K5团作其分子图，该图就一定不是平面图。那么，这样的图同化的最后结果一定是一个顶点数大于等于5的完全图；反过来，不含有K5团作其分子图的图，却不一定都是平面图，如K3，3图。但可以肯定，平面图中一定是会不含有K5团作其分子图的。虽然不含有K5团作其分子图的图同化时，不一定都会得到顶点数小于5的完全图（如含有一条不可同化道路的密度是4的非平面图的最小完全同态的顶点数就是大于等于5 的），但至少可以肯定不含有K5团作其分子图的平面图在同化时，是可以得到顶点数不大于4的完全图的，且这些完全图也都是平面图。
既然平面图同化的最终结果不会得到顶点数大于等于5的完全图，那么平面图同化的最终结果就一定只能是顶点数小于等于4的完全图了，这样的完全图在着色时，最多4种颜色也就够用了。按哈德维格尔的猜测想：“若图G是4色的，则G可以收缩为一个完全图K4”，图的最小完全同态的顶点数是4，则图原来就是4色的。这也就证明了四色猜测是正确的。

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

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


用还原法证明四色猜测
——四色猜测证明方法之十一
雷  明
（二○一六年十一月五日）

由于平面图中一定存在着度小于等于5的顶点，若把这些顶点从图中去掉时，图仍然还是一个平面图，但同时又会产生新的度小于等于5的顶点。再把新生成的度小于等于5的顶点去掉，又产生新的度小于等于5的顶点。就这样一直的把度小于等于5的顶点“去掉”下去，图最后将成为一个顶点数为1的K1图，只用一种颜色就够了。
现在再按“去点”时的相反方向往回走，先把最后一次去掉的那个度小于等于5的顶点还原上去，图中就有两个顶点，这时一定是K1图，两种颜色也就够用了；再把最后第二次去掉的那个度小于等于5的顶点还原上去，图中就有3个顶点了，最多三种颜色就够用了（因为这时图可能是一条道路，只用两种颜色，若是一个圈K3时，就得用三种颜色）；第三步再把最后第三次去掉的那个度小于等于5的顶点还原上去，图中就有4个顶点了，同样，也最多只用四种颜色就够用了；若按次序再还原上一个顶点时，这时图中就有5个顶点了，但这第5个顶点与前4个顶点的相邻关系可能是：
①　前4 个顶点间没有构成密度是4的K4团时，这四个顶点最多只占用三种颜色，第5个顶点虽然可以与前4个顶点均相邻，但至少仍有一种颜色可以着上，图的色数没有大于4；
②　前4个顶点若构成了密度是4的K4团时，这四个顶点就占用完了四种颜色，但第5个顶点最多却只能与前4个顶点的3个顶点相邻，否则图将成为非平面图，会出现在顶点之外边与边的相交叉。这时，第5个顶点仍有一种颜色可以着上，图的色数没有大于4。
按次序再还原第6个顶点时，与第5个还原顶点相同，该顶点最多只可能与图中的K4团有3个顶点相邻，或者前5个顶点构成的图的密度小于4时，都至少还有一种颜色可以着上；
以后再按次序还原的顶点，与已还原的顶点的相邻关系，也都只能是以上的两种情况，所还原的顶点均可着以四种颜色之一。一直到把原图中的所有顶点都还原完毕，图中都不会出现使用四种颜色以外的第五种颜色的情况。这也就证明了四色猜测是正确的。

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

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


用断链法证明四色猜测
——四色猜测证明方法之十二
雷  明
（二○一六年十一月五日）

一个构形的待着色顶点，如果其围栏顶点占用的颜色数未达到4时，该待着色顶点都是可以着上四种颜色之一的；如果围栏顶点已占用完了四种颜色，则必须想办法从围栏顶点中空出一种颜色来，然后给待着色顶点着上。如何空出颜色，这就得灵活的运用坎泊的颜色交换技术了。
用坎泊的颜色交换技术空出颜色来给待着色顶点的原则是：首先要看，在以待着色顶点为中心顶点的轮中，对角顶点间的颜色所构成的色链是不是连通链，如果不是连通的链时，才可以进行交换，也才能空出颜色给待着色顶点。而如果是连通链时，即就是交换了这种链也是空不出颜色来的。
4—轮构形中只可能有一条连通链，该构形一定是可以通过坎泊的颜色交换，空出一种颜色给待着色顶点着上的。而5—轮构形的情形就不同了，其中有可能有两条连通链的可能。若两链只有一个共同的起点，或是只有一个交叉顶点时，也一定是可以通过坎泊交换空出颜色来给待着色顶点的。而只有当两条连通链既有共同的起点，又有交叉顶点时，则难以通过交换5—轮对角链的办法解决问题。这种情况怎么办？可以想到，既然不连通的链是可以交换的，那么是否可以把已连通的链变成不连通的呢？完全可以。没有了连通链，或者只有一条连通链，一定是可以通过交换空出颜色给待着色顶点的。这种方法我们叫做“断链法”。
断链方法的原理是：用四种颜色A、B、C、D所能构成的链有六种，即A—B、A—C，A—D，B—C，B—D和C—D六种，如果有A—B链是连通的时，则该链中的A和B在该链以外，只能与C和D相邻，构成A—C链和A—D链或者B—C链和B—D链，从A—B链上的任何一个A或B顶点起，开始交换上述的A—C链或A—D链（或者B—C链或B—D链）中的一种，都可以使A—B链上的被交换的顶点A或顶点B变成C或D，使A—B链断开。这样就可以对5—轮轮沿中的顶点A或B施行A—B链的交换，空出A或B来给待着色的5—轮中心顶点着上。
我们在对赫渥特图，敢峰—米勒图的着色中，使用的就是这种方法。可以说任何平面图中的任何链都是可以通过这一方法“断开”的。连通链断开了，就可以通过坎泊交换空出已用过的四种颜色之一，给待着色顶点着上。所以也就可以说明任何平面图着色时是不会用到第五种颜色的。这也就证明了四色猜测是正确的。
雷  明
二○一六年十一月五日于长安
注：此文已于二○一六年十一月五日在《中国博士网》上发表过，网址是：


赫渥特的地图着色公式是正确的
——四色猜测证明方法之十三
雷  明
（二○一六年十一月五日）

我们虽然不知道赫渥特的地图着色公式是怎么得来的，但我们却可以用严密的数学推导而得出该公式。
1、赫渥特地图着色公式的推导
顶点数v≥3的图都有3f≤2e（f是面数，e是边数）的关系，把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2（1－n）（n是图的亏格）中得
    e≤3v－6（1－n）（v≥3）                     （1）
注意，这里对图的亏格可是没有任何限限制的。再把完全图边与顶点的关系e＝v（v－1）/2代入（1）式中得
v（v－1）/2＝3v－6（1－n）
v2－7v＋12（1－n）≤0                         （2）
解这个一元二次不等式（2），得其正根是
v≤（7＋√（1＋48n））/2  （v≥3）
由于顶点数v必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞ （v≥3）        （3）
（3）式中暂用＜ ＞表示其中的数字向下取整。这就是可嵌入亏格为n的曲面上的最大完全图的顶点数。因为完全图的色数γ就等于其顶点数v，即有γ完＝v，所以又有多阶曲面上图的色数是
γ图≤＜（7＋√（1＋48n））/2＞ （v≥3）      （4）
这就是赫渥特的多阶曲面上的地图着色公式（其实这个公式我们在四色猜测证明方法之三《平面（球面）上可嵌入完全图的顶点数不大于4》一文中已经看到过），这里只是色数的一个界限。
2、四色猜测是正确的
上面的赫渥特的地图着色公式是适用于任何亏格的图的。四色猜测研究的对象是平面（球面）上的图的着色，平面（球面）图的亏格等于0，代入（4）式中得：γ平≤4；而七色定理是研究轮胎面（环面）上的图的着色，其亏格等于1，代入（4）式中得：γ环≤7。把其他的曲面的亏格代入（4）式中时，都可得到各亏格下的曲面上图的着色数的界限。四色问题研究的是平面图，正好平面图的色数的界限是≤4，这也就证明了四色猜测是正确的。
3、林格尔公式与赫渥特地图着色公式互为反函数
林格尔公式n＝〔（v－3）（v－4）/12〕（v≤3）是不同顶点数的完全图的亏格数（这里也暂用方括号〔 〕表示其中的数字向上取整）。它和赫渥特的地图着色公式同样都是上面（2）式中的一元二次不等式的另一种形式的解。在（2）式是v2－7v＋12（1－n）≤0里，其中有两个可变的参数，一是图的顶点数，一是图的亏格。两个参数都可作为自变量，对另一个作函数求其值。上面赫渥特的地图着色公式就是把图的亏格n作自变量，求某亏格n下的最大完全图的顶点数v值的公式；而林格尔公式则是把图的顶点数v作自变量，求顶点数是v的完全图的亏格n的，由于某一数量顶点的完全图的亏格只可能是一个，所以林格尔公式中只用了等式。这两个公式是互为反函数的。不能用来相互证明的。在沙特朗的《图论导引》一 中用了林格尔公式去证明赫渥特地图着色公式是不合适的。
4、赫渥特地图着色公式是没有附加条件的
当时赫渥特是怎么得到他的地图着色公式的，我们不可能知道，也可能是赫渥特自已的经验总结的公式吧。由于赫渥特本人对他的赫渥特图不能进行4—着色，所以即就是该公式对于亏格为0时，色数小于等于4，他也只能在公式的后面附加亏格大于0的条件。而后人在证明该公式正确与否时，也不加思索的在证明之前就排除了亏格等于0的可能，这是不应该的。沙特朗，韦斯特，哈拉里的证明中都是在未证明之前就排除了亏格为0的情况，那怎么能说明赫渥特的公式对于亏格为0的图是不适用的呢。我还认为这种可以经过严密数学推导而得到的结论，是不需要再进行证明的，因为推导过程中每一步都是符合逻辑的。

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

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


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

雷明85639720

,,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，