《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（四）

雷明85639720

（接上贴）

三十多年研究四色问题的总结：《四色猜测的手工证明——证明四色猜测的十多种方法汇编》（四）

用增加图的色数证明四色猜测的两种方法
雷  明
（二○一七年三月十一日）

1  根据不可同化道路原理，证明四色猜测是正确的
1、1  作一个图的色数比原图的色数大1的方法之一——不可同化道路法：
这里的“同化”即图论中的“收缩”，且只是指不相邻顶点间的收缩。“不可同化道路”是指图中某最大团外的一条道路，该道路总有一个顶点同化不到最大团中去。

若在一个最大团Kn外有一条道路，这条道路的所有顶点都与最大团中的同一个Kn－2团的各顶点均相邻，同时道路的两个端点顶点又都与最大团中另一个K2团中的一个顶点相邻。这样，道路中除了两个端点顶点只能向那个K2团的某一个顶点同化外，道路中的其他顶点均是可向这个K2团中的任一个顶点同化（如图1）。
当道路的两个端点顶点分别与K2团中的一个顶点相邻时（如图1，a），同时道路又是奇数顶点时，道路中总是有一个顶点同化不到最大团中去：而当道路的两个端点顶点都与K2团中的同一个顶点相邻时（如图1，b），同时道路又是偶数顶点时，道路中也总是有一个顶点是同化不到最大团中去的。
1、2  色数为n的图一定可以同化为一个Kn图：
根据已经证明是正确的哈德维格尔猜想，一个色数为n的图，一定是可以同化为一个Kn图的。因为图中不相邻的顶点才可以使用同一颜色，而不相邻的顶点也是可以同化为一个顶点的，所以哈德维格尔猜想是正确的。由色数为n的图同化成的Kn图，就是该图的最小完全同态，其顶点数n就是图的色数。图的最小完全同态是一个完全图，而完全图的色数也就是其顶点数。
现在我们对图的完全同态Kn用不可同化道路原理使其色数增大，只要不可同化道路系统不是非平面图，图的色数又不大于4时，就说明四色猜测是正确的；否则，若系统仍是平面图，而只要有一个图的色数是大于4时，四色猜测就是错误的。
1、3  对各种团作不可同化道路：
K1团，色数是1，它本身就是一个平面图，图中就只有一个顶点，没有任何边，不可能存在不可同化道路。也没有任何一个图是可以同化成K1图的；
K2团，色数是2，作不可同化道路并同化后是一个K3团，仍是平面图（如图2）。色数是3，虽比原来增大了1，但却小于4；
K3团，色数是3，作不可同化道路并同化后是一个K4团，也是平面图（如图3）。色数是4，虽也比原来增大了1，但却也不大于4；
可见顶点数小于4的团，作不可同化道路并同化后的图仍然是平面图，其色数都不大于4。


K4团作不可同化道路时，图中就出现了交叉边，变成了非平面图，同化后则是一个K5团（如图4），不再是四色猜测所研究的对象了。所以说平面图中的K4团是没有不可同化道路的。
    因为K5团本身就不是平面图，本身就不是四色问题研究的对象，所以这里也就不对其再作不可同化道路了。
1、4  K4团作了不可同化道路后不再是平面图的证明：
K4团的顶点数是4，边数是6；不可同化道路Pn的顶点数是n，边数是n－1；K4团与Pn道路相邻的边数是2n＋2；整个系统的顶点数是4＋n，边数是6＋n－1＋2n＋2＝3n＋7；顶点数是4＋n的平面图最大边数只可能是3×（4＋n）－6＝3n＋6；显然3n＋7＞3n＋6，所以对K4团作了不可同化道路后，就不再是平面图了。

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

当图道路时，色数也是2，M—操作的结果，色数比原图大1是3，也不大于4，仍是平面图，但图中既有了4—圈，也有了5—圈，如图7；

当图是树（包括3—星这样最简单的树）时，色数也是2，M—操作的结果，色数比原图大1是3，虽不大于4，但却成了一个非平面图，如图8。已不再是四色猜测研究的对象了；
2、2、2        当图中有两个面的情况时：
图是一个3—圈（即K3图）时，色数是3，M—操作的结果，色数比原图大1是4，但不大于4，仍是一个平面图，图中不但有3—圈，也有了4—圈，如图9；
图是一个4—圈时，色数是2，M—操作的结果，色数比原图大1是3，虽不大于4，但却成了一个非平面图，如图10；也已不再是四色猜测研究的对象了；
图是一个5—圈时，色数是3，M—操作的结果，色数比原图大1是4，虽不大于4，但却也成了一个非平面图，如图11；也已不再是四色猜测研究的对象了；

可见，边数大于等于4的圈，进行了M—操作后的图，都会成为非平面图了，就不再是四色猜测研究的对象了。
2、3  除了3—圈（即K3团）以外的面数大于2的图进行M—操作后都不再是平成图的证明：
M—操作时，要先画一个星，该星只能画在一个面内。若图中有边数大于等于4的面（即4—圈）时，对这个4—圈进行M—操作后得到的是一个非平面图，所以含有边数大于等于4的圈的图，进行M—操作后的图就不再是平面图了；
若图是一个三角剖分图，所有面全是3—圈，M—操作中n—星的中心顶点u0一定要位于某个面以内，有关星点顶点若与位于该面边界上的顶点用边相邻时，是不会产生相交叉的边；但当n—星的有关星点顶点与位于该面边界以外的顶点用边相邻时，必然要产生相交叉的边，图也就变成了一个非平面图；
因此，图中面数是2的图，除了3—圈（即K3图）外，进行M—操作后的图均是非平面图；
含有轮的图中，其面数都是大于2的图，所以含有2—轮（有平行边的K3团或3—圈）和3—轮（即K4团）的图M—操作后的图也一定是非平面图。
2、4  除K1图外任可平面图都不可再进行第二次M—操作：
以上M—操作后的图仍是平面图的只有K1，K2，道路PN和K3（即3—圈），现在再看这些图是否还可以进行第二次M—操作：
K1图M—操作一次后，是一个K2图，是平面图（如图5），色数是2；这个图再进行一次M—操作后，一定是如图6那样的图，是一个5—圈，也是平面图，色数是3，仍不大于4；但因5—圈进行M—操作后是一个非平面图，所以K1图也只能进行两次M—操作；
K2图M—操作一次后，是一个5—圈（如图6），5—圈再进行M—操作后的图是一个非平面图，所以K2图也只能进行一次M—操作；
道路Pn进行M—操作一次后，所得图中既有4—圈，又有5—圈（如图7），因为这两种圈进行M—操作后的图都是非平面图，所以道路也只能进行一次M—操作；
3—圈（即K3图）M—操作一次后，图中既有3—圈，又有4—圈（如图9），因4—圈再进行M—操作后的图是非平面图，所以3—圈（即K3图）也只能进行一次M—操作。
除了以上这些图以外，其他任何平面图的面数都是大于等于2的。而除了3—圈外的任何面数大于等于2的平面图，在进行一次M—操作后的图都是非平面图，也就都不再是四色问题所研究的对象了。
2、5  四色猜测是正确的
以上我们对任意的平面图都进行了M—操作，M—操作后的结果仍是平面图的图的色数都是不大于4的，这就证明了开始的假设是正确的。任何平面图的色数都是不会大于4的，四色猜测是正确的。

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

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

公式推导证明四色猜测的三种方法
雷  明
（二○一七年元月三十一日）

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）
（1）式就是多阶曲面上图中顶点与边的关系。当图是完全图时，还应有e＝v（v－1）/2的关系，把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）式中暂用＜ ＞表示其中的数字向下取整。（3）式中的v就是可嵌入亏格是n的曲面上的完全图的顶点数。平面图的亏格是0，把n＝0代入（3）式中，得
v≤4                                         （4）
（4）式就是可嵌入亏格为0的平面上的完全图的顶点数。
公式（4）也可以直接从平面图的边与顶点的关系式e≤3v－6 （v≥3）得来。把完全图中边与顶点的关系e＝v（v－1）/2代入上式e≤3v－6中 得
v2－7v＋12≤0  （v≥3）                                  （5）
解（5）式这个一元二次不等式得
v1≤4和v2≤3                                                   （6）
由于v2≤3包含于 v1≤4中，所以实际只有一个根
v1≤4                                      （6＇）
与上面的（4）式完全相同。由于完全图着色，所需颜色数就是其顶点数，把（3）式中的顶点数v换成颜色数γ，则（3）式变成
γ≤＜（7＋√（1＋48n））/2＞ （v≥3）       （7）
把n＝0代入（7）式中，得
γ≤4                                        （8）
（8）式就是平面上完全图的色数，是不大于4的。因为图的色数就是其最小完全同态的顶点数，而任何平面图的最小完全同态也一定是平面上的完全图，所以（8）式也就是任意平面图的色数公式。因为γ≤4，这也就证明了四色猜测是正确的。
2、用平面（或球面）上不存在五色地图来证明
设在某亏格为n的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色地图。这个“国数最小的”地图中也就只应有γ个“国家”（这个“国数最小的”地图中的“国家”数γ，实际上就相当于图的最小完全同态的顶点数）。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与别的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域的总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这些边界线中，每条边界线都是计算了两次的，所以就有2e＝f（f－1）；又因为地图是一个3—正则图，即每一个顶点都连着3条边（即所谓的“三界点”），所以该地图的总边数也可以写成e＝3v/2，即有2e＝3v，从而有3v＝2e＝f（f－1）的关系。用区域数（即面数）f来表示顶点数v和边数e，则有v＝f（f－1）/3和e＝f（f－1）/2。把v＝f（f－1）/3和e＝f（f－1）/2代入到多阶曲面上图的欧拉公式v＋f－e＝2－2n则得到
f2－7f＋12（1－n）＝0                        （1）
解这个关于“国数最小的”地图中的区域（国家）数f的一元二次方程（1）得正根是
        f＝（7＋√（1＋48n））/2
因为区域数必须是整数，所以上式还得向下取整，得
        f＝＜（7＋√（1＋48n））/2＞                 （2）
式中用＜ ＞表示其中的数字向下取整。又因为f是两两均相邻的“国数最小的”地图的“国数”，即区域数，所以这个“国数最小的”地
图染色时也必须用与其区域数相同的颜色数，所以又有
        γ＝f＝＜（7＋√（1＋48n））/2＞             （3）
（3）式中当曲面的亏格为n＝0时，其两两区域均相邻的区域数和色数都是等于4的，即
γ＝f＝4                                      （4）
（4）式这个结果说明了平面地图中是不存在五个区域两两均相邻的情况的，即不存在五色地图。
（4）式实际上是当曲面的亏格为n＝0时，其两两区域均相邻的区域数f的最大值，当然色数γ也就是最大值了，即γ＝f≤4。也就是说（平面）地图着色的色数，是小于等于4的。这就证明了地图四色猜测是正确的。
地图中两两均相邻的区域的个数不大于4（即不存在五色地图）还可以直接用平面图的欧拉公式来证明。把把v＝f（f－1）/3和e＝f（f－1）/2代入到平面图的欧拉公式v＋f－e＝2中，则得到
f2－7f＋12＝0                                （5）
解（5）的一元二次方程得两个正根分别是
f＝4和f＝3
均小于5，也说明了平面地图中只能存在3个或4个区域两两相邻，而不存在5个区域两两相邻的情况，即不存在五色地图。
按坎泊的思想，只要能证明平面地图中不存在五色地图，那么地图四色猜测就是成立的。现在已经证明了平面地图中的却不存在五色地图，所以地图四色猜想就是正确的。地图四色猜测是正确的，那么给地图的对偶图——极大平面图的顶点着色，也就只要四种颜色就够用了。四色猜测是正确的。
3、用赫渥特地图着色公式来证明
顶点数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）式就是赫渥特的多阶曲面上的地图着色公式，它是适用于任何亏格的图的。四色猜测研究的是平面（球面）上的图的着色，把平面（球面）图的亏格等于0代入（4）式中得γ平≤4；这就证明了四色猜测是正确的。
4、林格尔公式与赫渥特地图着色公式是互为反函数的，可以相互推导，但不能用以相互证明
林格尔公式与赫渥特地图着色公式是互为反函数的，是可以相互推导的。林格尔公式n＝〔（v－3）（v－4）/12〕（v≥3）表示的是不同顶点数的完全图的亏格数（这里也暂用方括号〔 〕表示其中的数字向上取整）。它和赫渥特的地图着色公式同样都是上面（2）式中的一元二次不等式的解的一种形式。在（2）式的v2－7v＋12（1－n）≤0中，有两个可变的参数，一是图的顶点数，一是图的亏格。两个参数都可作为自变量，而把另一个作函数求其值。上面赫渥特的地图着色公式就是把图的亏格n作自变量，求某亏格n下的最大完全图的顶点数v值的公式；而林格尔公式则是把图的顶点数v作自变量，求该顶点数是v的完全图的亏格n的。由于某一顶点数的完全图的亏格只可能是一个，所以林格尔公式中只用了等式。这两个公式是互为反函数的，是可以相互推导的。不能用来相互进行证明，否则就成了循环论证。
当时赫渥特是怎么得到他的地图着色公式的，我们不可能知道。但我们在推导该公式的过程中，是没有对亏格附加任何条件的。这种可以经过严密数学推导而得到的结论，是不需要再进行证明的，因为推导过程中每一步都是符合逻辑的。严密的数学推导的过程，就是证明的过程。因为林格尔公式与赫渥特地图着色公式是互为反函数的，所以用林格尔公式证明赫渥特的地图着色公式，或者反过来又用赫渥特的地图着色公式证明林格尔的公式，都是错误的。

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

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

（未完，接下贴）

雷明85639720

，，，，

雷明85639720

谢谢了。

雷明85639720

，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

就观盛道

鼓励一下，帖子非常好