四色猜测与欧拉公式

雷明85639720

四色猜测与欧拉公式
雷  明
（二○一五年十一月十二日）

【摘  要】从不同的角度用不同的方法均能用欧拉公式推出四色猜测的表达式，说明了四色猜是正确的。
【关键词】四色猜测  地图  平面图  多阶曲面  曲面的亏格  欧拉公式

    1、地图四色猜测的证明：
按照坎泊（Kempe）的思想，如果能证明不存在极小五色地图，就可以说地图四色猜测是正确的。所谓极小五色地图就是由五个国家两两均相邻的地图。设地图中两两均相邻的国家数是f，这样的地图着色时，一定要用到与其国家数相同的颜色数，即有γ＝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同时代入到平面图的欧拉公式v＋f－e＝2则得到
f2－7f＋12＝0
解这个关于f的一元二次方程得两个正根分别是
        f＝4和f＝3
两个根中，由于f＝4大于f＝3，所以把两个根合起来写就是f≤4，也小于5，这就证明了地图中是不会存在五个国家两两相邻的情况的。
    由于γ＝f，所以又有γ≤4。这就是地图的四色猜测，说明了猜测是正确的。
当把v＝f（f－1）/3和e＝f（f－1）/2同时代入到多阶曲面上图的欧拉公式v＋f－e＝2－2n（式中n为曲面的亏格）则得到
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的曲面上，两两均相邻的国家中的“国数”最大者。该曲面上还会存在比f少的区域也是两两相邻的，所以上式还可以再增加上“不等式部分”，即
        γ＝f≤＜（7＋√（1＋48n））/2＞
这就是赫渥特地图着色公式的全貌了，其中既有等式又有不等式。
式中当曲面的亏格为n＝0时，其色数γ＝f≤4，这就是地图中两两均相邻的区划数，是不大于4的，这就证明了地图中是不存在5个区域两两均相邻的现象的。这也就证明了地图四色猜测是正确的。
2、平面图四色猜测的证明：
地图是一个平面图，其对偶图也是一个平面图。给地图中面的染色实际上就是给其对偶图（平面图）的顶点着色。
不相邻顶点是可以同化成一个顶点的（同化是把两个不相邻顶点凝结在一起的过程。相当于图论文献上所说的“收缩”。由于在图论文献中，收缩有相邻顶点间的收缩和不相邻顶点间的收缩，为了便于区别，所以我把不相邻顶点间的收缩称为“同化”。），任何图同化的最终结果一定是一个顶点数最少的完全图，也叫图的最小完全同态。由于任何图的色数就等于其最小完全同态的顶点数，所以也有γ＝f的关系。
设平面图的最小完全同态为Kv。把任意图中面与边的关系3f≤2e代入平面图的欧拉公式v＋f－e＝2中得
    3v－e≥6
再把完全图的边与顶点的关系e＝v（v－1）/2代入上式中得
        v2－7v＋12≤0
解这个关于平面图最小完全同态的顶点数v的一元二次不等式得
        v1≤4和v2≤3
其中v1≤4包含v2≤3，所以该不等式实际上只有一个根v1≤4，即任何平面图的最小完全同态的顶点数都是小于等于4的。
因为任何图的色数都等于其最小完全同态的顶点数，所以有γ＝v，也有γ≤4 的结论。这就是平面图的四色猜测。平面图的四色猜测也得到证明是正确的。
若把任意图中面与边的关系3f≤2e代入多阶曲面上图的欧拉公式v＋f－e＝2－2n中则得到
3v－e≥6－6n
再把完全图中边与顶点的关系e＝v（v－1）/2代入上式得
        v2－7v＋12（1－n）≤0
解这个关于完全图（即亏格为n的图的最小完全同态）的顶点数v的一元二次不等式，得正根是
v≤（7＋√（1＋48n））/2
由于顶点数必须是整数，所以上式也得向下取整，得
v≤＜（7＋√（1＋48n））/2＞
式中用＜ ＞表示其中的数字向下取整。因为完全图的色数就等于其顶点数，所以又有
γ≤＜（7＋√（1＋48n））/2＞
这就是赫渥特的多阶曲面上的地图着色公式。当n＝0时，上式的计算结果是γ≤4，这就是平面图的四色猜测。平面图的四色猜测得到证明是正确的。


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

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

雷明85639720

,,,,,,,,,,