[原创]从欧拉公式到四色猜测的证明

雷明85639720

[watermark]

从欧拉公式到四色猜测的证明
雷  明
（二○一○年九月六日）
本方法是纯粹用数学推导的办法，从曲面上的欧拉公式推导出了任意平面图着色的色数一定是小于等于4的。也就是相当于对四色猜测进行了证明。
1、曲面上图的欧拉公式
已经得到证明是绝对正确的可嵌入到任何亏格曲面上的图的欧拉公式如下：
     v＋f＝e＋2－2n        （1）
式中v、f、e、n分别是图的顶点数、面数、边数和曲面的亏格（也就是图的亏格，这里曲面的亏格应是图所可嵌入的曲面的最小亏格）。其证明方法可参见人民邮电出版社2007年9月份出版的，［美］Gary• Chartrand和Ping•Zhang编著，范益政、汪毅、龚世才、朱明翻译的《图论导引》（《lntroduction  to  Graph  Theory》）一书。这个公式也适用于亏格n为0的平面图，当n＝0时公式变成
    v＋f＝e＋2              （2）
公式（2）就是我们平时所说的平面图的欧拉公式。
2、任意图的顶点数
从公式（1）的欧拉公式可以求出任意图的顶点数与其亏格的关系。
能嵌入到与图的亏格n相同的曲面上的图，其顶点v、边e和面f间的关系是一定能适合该曲面上的图的欧拉公式（v＋f－e＝2－2n）的。设f个面分别为f1，f2，……，ff，用ei（1≤i≤f）表示面fi边界上的边数，所以有ei≥3，又因为每一条边均是属于两个面所共有，所以有
   3f≤ ≤2e                （3）
图论中我们又知道任意图的边数与顶点数有如下关系
e≤v（v－1）/2              （4）
（3）式和（4）中的等式对应的都是完全图，而不等式对应的则是非完全图。把（3）式和（4）式分步代入（1）式的欧拉公式
v＋f＝e＋2－2n             （1）
中后，就可得到任意图顶点数与其亏格的关系。
    推导步骤如下：
首先把（3）式f≤2e / 3代入公式（1）v＋f＝e＋2－2n中，得
    v＋ ≥e＋2－2n
整理后得到
        3v＋2e≥3e＋6－6n
        3v≥e＋6－6n         （5）
再把公式（4）式e≤ 代入到（5）式3v≥e＋6－6n中，得
3v≥ ＋6－6n
整理后再得到
6v≥v2－v＋12（1－n）
        －v2＋7v－12（1－n）≥0
        v2－7v＋12（1－n）≤0（6）
解（6）中该关于顶点数v的一元二次方程得
        v1≤ ≤
        v2≤ ≤
由于在v2≤ 中，当n≥1时，v2≤ ≤0，而任何图的的顶点数都是不会小于1的，v＜0不符合题意，所以舍去不要。该一元二次方程也只有一个根v1≤ 。即
v≤                        （7）
又因为图的顶点数必须是整数，且（7）式中不等号又是小于等于号，所以该式还得向下取整，得
        v≤                 （8）
（8）式就是任意图的顶点数与图的亏格的关系。
    3、赫渥特的地图着色公式
如果上面（8）式中的顶点数为v的图是一个完全图KV，则其色数就等于其顶点数，所以就有这个可嵌入到亏格为n的曲面上的完全图（图的亏格也是n）KV的色数就是v；如果该顶点数为v的图是非完全图，那么其色数一定比其顶点数要小。由此可以得出顶点数同为v的图，其色数都一定是小于等于其顶点数的。即有
    γn≤v≤
即
γn≤                       （9）
（9）式就是赫渥特多阶曲面上的地图着色公式。
1890年赫渥特早就得到了多阶（任何亏格）曲面上的地图着色公式，这个公式断言，能嵌入亏格为n的曲面上的所有图的色数是：
γn≤ （n≥1）              （10）
（10）式中n也是曲面的亏格数（也是图的亏格），γn是能嵌入亏格为n的曲面上的所有图的色数。 也表示其内数字向下取整。由于当时赫渥特对自已所构造的图——Haewood—图（平面图，其亏格是n＝0）不能进行4—着色（其实，该图是可以4—着色的），所以就对他的公式附加了成立的条件n≥1。
这时由欧拉公式直接推导出来的公式（9）并没有附加任何条件，实际上就是指亏格大不于等于0的图，即n≥0。
4、赫渥特地图着色公式的两种含义
    公式（9）有两种含义，一是能嵌入任意亏格曲面上的图的色数一定是γn≤ ，比如，K1，K2，K3，K4，K5，K6和K7的色数分别是1，2，3，4，5，6和7，都小于等于7，他们都以可嵌入到亏格为n＝1的轮胎面上；另一是任意亏格的图的色数也一定是γn≤ ，比如，K1，K2，K3和K4的色数分别是1，2，3，4，都小于等于4，他们都是亏格为n＝0的平面图；K5，K6和K7的色数分别是5，6和7，都小于等于7，他们都是亏格为n＝1的非平面图。
5、四色猜测的证明
公式（9）和（10）既然都是任意亏格下的曲面上的地图着色公式，那么其对于亏格为0的平面图也应该是适合的。的确，当n＝0时，公式（9）和公式（10）的结果都是γn≤4，这就是四色猜测的数学表达式。这就是说，任何平面图着色时，其色数一定是小于等于4的。这时我们就可以把（9）和（10）式的赫渥特公式改写成
    γn≤ （n≥0）         （11）
这时公式才是正确的，因为现在它已把亏格为0的平面图也包括在内了，这也就使猜测得到了证明是正确的。

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