不画图不着色证明四色猜测的各种方法

雷明85639720

不画图不着色证明四色猜测的各种方法
雷  明
（二○一五年元月十七日）

1、不画图不着色证明四色猜测的思想产生的历史渊源
四色猜测一八五二年提出，一八七九年坎泊创造了颜色交换技术并宣布他证明了猜测是正确的，一八九○年赫渥特构造了赫渥特图，因他们不能对其进行4—着色而又否定了坎泊的证明。一九九○年我国的雷明先生与英国的米勒分别都对赫渥特图在原着色的基础上，采用了坎泊所创造的颜色交换技术，成功的对其进行了4—着色。但雷明认为这并不能说明四色问题就得到了解决，而在一九九二年公开提出了要使四色问题得到彻底的解决，就必须采用不画图不着色的办法对其进行证明。而米勒从他们对赫渥特的4—着色中，也看到了解决四色问题有了希望。但随后他们又构造了一个米勒图，用他们的方法又不能对其进行4—着色。所以他们又放弃了他们原来试图解决四色问题的打算。这就更加证明了雷明提出的走不画图不着色证明四色猜测的思想是正确的。雷明先生与张彧典先生分别经过对米勒图的研究，二○一○年，也都用坎泊的颜色交换技术对其进行了4—着色。但到此时，张彧典已认为再没有别的构形了，也不可能会有人再提出新的图不能进行4—着色了。而雷明则不这样认为，他认为仍然有可能在以后会有人再提出新的图来否定现有的所谓“证明”，而仍然坚持他提出的走不画图不着色证明四色猜测的道路。现在他的目标已经达到，本文就集中的体现了这一目标实现的结果。
2、不画图不着色证明四色猜所依据的理论根据
不画图不着色证明四色猜测的理论依据就是任何图的色数就等于其最小完全同态的顶点数。
把图中不相邻的顶点凝结到一起的过程叫做同化。每次同化后所得到的图叫原图的一个同态。一个图经若干次同化后一定可得到一个再不可能再进行同化的完全图，这就叫完全同态。同一个图可能会有多个完全同态，但其中总有一个完全同态的顶点数是最少的，这个同态就是该图的最小完全同态。因为不相邻的顶点可以着以同一种颜色，最小完全同态的每一个顶点都代表着若干个互不相邻的顶点，而完全同态着色时所用的颜色总数一定是与其顶点数相同的，所以图的最小完全同态的顶点数就是该图顶点着色的色数。图论大师哈拉里在其著作《图论》一书中也有这样的结论。
例如，一个有4个顶点的P4道路，如果把两个端点顶点凝结在一起，则是一个K3图，如果把顶点1和3凝结在一起，把顶点2和4凝结在一起，则是一个K2图，这个K2图就是这个P4道路的最小完全同态。完全同态K2图有两个顶点，着色时只需要两种颜色，所以P4道路的色数也就是2。
同化作为一种求图最小完全同态的方法，这里也必须再说明一下正确的同化原则。要使同化所得到的结果是某图的最小完全同态，就必须严格按照这一原则去实施。这一原则就是：要同化的两个不相邻顶点之间的距离是最短的。即要同化的两顶点之间最多只能相隔一个顶点。按这一原则去实施了，所得到的结果一定是某图的最小完全同态；如果不按这一原则去实施，则得到的完全同态就不一定是所求图的最小完全同态了。
3、第一种证明方法：多阶曲面上图的欧拉公式推导法
我们已经知道在任何图中都有3f≤2e即f≤2e/3的关系，任何完全图的边与顶点有e＝v（v－1）/2的关系。其中v、e、f分别是图的顶点数、边数和面数。
设任意图的最小完全同态的顶点数是v，我们先把f≤2e/3代入到多阶曲面上图的欧拉公式v＋f－e＝2－2n（这里n是多阶曲面的亏格，也是图的亏格）中，得
v＋2e/3－e≥2－2n
3v＋2e－3e≥6－6n
3v－e－6（1－n）≥0
再把e＝v（v－1）/2代入到上面的不等式3v－e－6（1－n）≥0中，得
3v－v（v－1）/2－6（1－n）≥0
6v－v2＋v－12（1－n）≥0
7v－v2－12（1－n）≥0
v2－7v＋12（1－n）≤0
解这个关于图的最小完全同态的顶点数v的一元二次平等式，得
        v≤（－（－7）±√（（－7）2－4×（－12（1－n））））/2
         ≤（7±√（1＋48n））/2
即
        v1≤（7＋√（1＋48n））/2
        v2≤（7－√（1＋48n））/2
因为图的顶点数必须是正数，而在v2≤（7－√（1＋48n））/2中，当n≥1时，则v2≤0，不符合题意，舍去不要。所以该一元二次不等式实际只有一个根v1≤（7＋√（1＋48n））/2。又因为图的顶点数必须是整数，所以对v1≤（7＋√（1＋48n））/2还得向下取整，即有
        vn≤＜（7＋√（1＋48n））/2＞
式中＜ ＞表示其中的数字向下取整。也由于任何图的色数就等于其最小完全同态的顶点数，所以上式就也可以表示成
γn≤＜（7＋√（1＋48n））/2＞
这就是赫渥特的地图着色公式。式中当图的亏格n＝0时，有γn≤4，这就是四色猜测。
也可以直接用平面图的欧拉公式进行推导：
设平面图的最小完全同态（这也是一个图）的顶点数是v，我们先把f≤2e/3代入到平面图的欧拉公式v＋f－e＝2中，得
v＋2e/3－e≥2
3v＋2e－3e≥6
3v－e－6≥0
再把e＝v（v－1）/2代入到上面的不等式3v－e－6≥0中，得
3v－v（v－1）/2－6≥0
6v－v2＋v－12≥0
7v－v2－12≥0
v2－7v＋12≤0
解这个关于平面图的最小完全同态的顶点数v的一元二次不等式，得
        v≤（－（－7）±√（（－7）2－4×（－12）））/2
         ≤（7±1）/2
即
        v1≤4
        v2≤3
这两个根中，v1≤4包含v2≤3，实际上只有一个根，即v1≤4。因为这里的v是任意平面图的最小完全同态的顶点数，所以任何平面图的色数是γ0≤4，这也就是四色猜测。与上面的结论是相同的。
既然任何平面图的最小完全同态的顶点数都是小于等于4 的，那么可以肯定的说，这些完全同态也一定都是平面图。完全同态也是完全图，而在平面图中的完全图也只有K1, K2, K3, K4四种，它们的顶点数分别是1、2、3、4，这就是说任何平面图的最小完全同态的顶点数都是小于等于4的。按哈拉里说的任何图的最小完全同态的顶点数就是该图的色数的结论，那么任何平面图的色数也就是小于等于4 的了，即γ平（γ0）≤4，这也就是四色猜测。
4、第二种证明方法：图的最小完全同态的亏格分析法
上面已经知道任何图的色数都等于其最小完全同态的顶点数，最小完全同态就是一个完全图，任何图都有其亏格，那么图的最小完全同态的亏格与其原图的亏格之间有什么关系呢。
上面说了，图的最小完全同态是通过同化运算得来的，且同化运算中图的顶点数与边数是在处不断减少的过程中。可以说在同化过程中，图本身也是处在一个由复杂图到简单图的变化过程中。这一变化表现在最小完全同态的顶点和边数都是比原图减少了的，而只有当图是完全图时，本身不需要同化且不能同化，所以其最小完全同态的顶点数、边数都才不会发生变化的。
最小完全同态的顶点数与边数都比原图中少了，那么其亏格会不会发生变化呢，肯定的说，会的。比如K3,3图的亏格是1，其最小完全同态是K2，亏格则是0，比K3,3图的亏格小了；那么有没有最小完全同态的亏格反而大于原图的亏格呢。我们不仿假设有这样的情况。采用反证明法进行证明。既然最小完全同态的亏格大于原图的亏格，那么它一定是不能嵌入到与原图同亏格的曲面上的。这一点是不可含乎的。这也就说明了这一假设也是不可能成立的。因为同化过程本身就是在与原图同亏格的曲面上进行的，最小完全同态仍是嵌入在原亏格的曲面上的，最小完全同态中也没有出现交叉边，应该说该最小完全同态还是嵌入在该亏格曲面上的图，其亏格并没有增大。
比如，我们用橡皮筋结一个亏格为n的图，同时也把该图嵌入一个与其亏格相同的曲面上。按照正确的同化原则进行同化，只要一出现平行边就把其中一条剪掉，只留一条，以保持图一直是一个单纯图。直到最后图中既无不相邻顶点，又无平行边时，这时所剩的完全图就是原图的最小完全同态。现在要问，原图所嵌入的曲面的亏格，是否就是该最小完全同态的亏格呢，还仍然不能确定。因为图的亏格是其所能嵌入的所有曲面的最小亏格，而原图所嵌入曲面的亏格不一定就是该最小完全同态所能嵌入的曲面的最小亏格。比如，K3,3图的最小完全同态K2图虽然仍可嵌入在亏格是1 的环面上，但1并不是K2图的亏格，K2图的亏格应是0，这也就是说K3,3图的最小完全同态的亏格应是0。从以上的分析看，至少可以肯定，图的最小完全同态的亏格一定是不会大于原图所能嵌入的曲面的亏格的，即最小完全同态的亏格一定是小于等于原图的亏格的。这与原假设的“最小完全同态的亏格大于原图的亏格”便设产生了矛盾，应否定假设。所以就有图的最小完全同态的亏格一定是小于等于原图的亏格的。
既然任何图的最小完全同态的亏格一定是小于等于其原图的亏格的，原图的色数又等于最小完全同态的顶点数，那么也就有任何平面图的最小完全同态的亏格一定是等于0的平面图的结论。而亏格为0的平面图中也只有K1, K2, K3, K4四种完全图，其顶点数都不大于4，所以说任何平面图的色数也一定都不会大于4。这也就证明了四色猜测是正确的。

以上两种方法均是从对图的顶点着色的角度出发进行证明的。由于地图是一个平面图，其对偶图也是一个平面图，所以给平面图的顶点着色，也就相当于给地图的面的染色。平面图的四色猜测得到了证明是正确的，也就有地图的四色猜测也是正确的。
下面我们再从对地图的区域（面）的染色角度出发对地图四色猜测进行证明。
5、第三种证明方法：用坎泊的“国数最小的”地图进行证明
设在某亏格为n的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色的地图。那么这个“国数最小的”地图中也就应有γ个“国家”。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与另外的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这f（f－1）条边界线中每条边界线却都是计算了两次的，则这个地图中的“边界线”的总条数，也即总边数应该是e＝f（f－1）/2。又因为地图是一个3—正则图，即每一个顶点都连着3条边，也就是所谓的“三界点”，所以该地图的总边数也可以写成e＝3v/2，从而有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则得到
    f（f－1）/3＋f－f（f－1）/2＝2－2n
    2f（f－1）＋6f－3f（f－1）＝12－12n
    6f－f（f－1）＝12－12n
6f－f2＋f＝12－12n
7f－f2＝12－12n
f2－7f＝12n－12
f2－7f＋12－12n＝0
f2－7f＋12（1－n）＝0
解这个关于“国数最小的”地图的区域数f的一元二次方程得正根是
        f＝（7＋√（1＋48n））/2
因为区域数必须是整数，所以上式还得向下取整，得
        f＝＜（7＋√（1＋48n））/2＞
式中用＜ ＞表示其中的数字向下取整。又因为f是两两均相邻的“国数最小的”地图中的“国数”，即区域数，所以这个“国数最小的”地图染色时也必须用与其区域数相同的颜色数，所以又有
        γ＝f＝＜（7＋√（1＋48n））/2＞
这就是赫渥特的地图着色公式的“等式部分”。
从以上的讨论看，这个区域数f只是某一亏格为n的曲面上“国数最小的”地图中的“国数”最大者。若从这个“国数最小的”地图中去掉一条边，或者去掉一个“三界点”顶点及其所连的3条边，该地图中的区域数就都会减少。这个“国数最小的”地图原来是一个区域染一种颜色，那么现在区域数少了，所用的颜色数也就会减少下来。所以上式还可以再增加“不等式部分”，即
        γ＝f≤＜（7＋√（1＋48n））/2＞
这就是赫渥特地图着色公式的全貌了，其中既有等式又有不等式。式中当曲面的亏格为n＝0时，其色数γ＝f≤4，这就是地图四色猜测。这与我们以前用对图的顶点着色推导出的赫渥特的地图着色公式是完全相同的。
    也可以直接用平面图的欧拉公式求出：
如果直接把v＝f（f－1）/3和e＝f（f－1）/2代入到亏格为n＝0的平面图的欧拉公式v＋f－e＝2中则得到
f2－7f＋12＝0
解这个关于f的一元二次方程得正根是
        f＝（7＋√1）/2
         ＝（7＋1）/2
        ＝4
这里的f＝4就是平面或球面上色数小于等于4的两两均相邻的“国数最小的”地图中的“国数”最大者，这些地图染色时必须用与其区域数相同数目的颜色，同样也有
    γ＝f≤4
这也就是地图四色猜测。

以上我们实际上是用了5 种方法分别进行证明的，都说明了四色猜测是正确的。

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

注：此文已于二○一五年元月十七日在《中国博士网》上发表过。