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

雷明85639720

[watermark]

从欧拉公式到四色猜测的证明
——一种纯公式推导的证明方法
雷  明
（二○一○年二月十七日）
本方法是纯用数学公式推导的办法推导出了任意平面图着色的色数一定是小于等于4的。
1、曲面上图的欧拉公式
已经得到证明是绝对正确的可嵌入到任何亏格曲面上的图的欧拉公式如下：
    v＋f＝e＋2－2n                               （1）
式中v、f、e、n分别是图的顶点数、面数、边数和曲面的亏格（也就是图的亏格）。这里曲面的亏格应是图所可嵌入的曲面的最小亏格。其证明方法可见人民邮电出版社2007年9月出版，美国Gary•Chartrand  Ping•Zhang编著，范益政、汪毅、龚世才、朱明翻译的《图论引导》一书。
2、任意图的亏格
任何图的亏格就是其所能嵌入的曲面的最小亏格。
通过曲面上的图的欧拉公式是可以推导出任何图所能嵌入的曲面的最小亏格。推导过程如下：
能嵌入到与图的亏格n相同的曲面上的图，其顶点v、边e和面f间的关系是一定能适合该曲面上的图的欧拉公式（1）（v＋f－e＝2－2n）的。
设f个面分别为f1，f2，……，ff，用ei（1≤i≤f）表示面fi边界上的边数，所以有ei≥3，又因为每一条边均是属于两个面所共有，所以有
3f≤ ≤2e                                 （2）
（2）式中，2e是图中所有边的2倍，包括悬挂边和桥边在内，而 却只是所在面（即圈）的边界条线的总和，所以有 ≤2e，又由于任何面的边界数都大于等于3，所以在面数相同情况下，就有3f≤ ，即有3f≤ ≤2e的关系。所以又有
3f≤2e  和  f≤2e / 3                          （3）
上面的3f≤2e和f≤2e / 3也可以这样来理解：如果图的所有面均是3—边形面，则有3f＝2e和f＝2e / 3，这是相同顶点时的图中边和面最多的情况；如果图中的顶点数不变，而含有边数大于3的多边形的面时，则有3f＜2e和f＜2e / 3。二者写在一起，这时就有3f≤2e和f≤2e / 3。把（3）式中的f≤2e / 3代入到曲面上的图的欧拉公式（1）v＋f－e＝2－2n中，得
        v＋ －e≥2－2n
两边同除以2得
         ＋ － ≥1－n
         ≥1－n
         － ≥1－n
两边同乘以－1，改变不等式符号的方向
         － ≤－1＋n
解关于n的方程并移项整理得
        n≥ － ＋1
图或曲面的亏格都必须是整数，所以上式还得向上取整，得
        n≥ （v≥3）                         （4）
该公式也就是任意图的亏格与顶点v和边e有关系。
公式（4）还可以变形成
    n≥ （v≥3）                       （4＇）
（4）和（4＇）式中的 表示其内的值向上取整。
3、完全图的亏格
1968年由Gerhard•Ringel和J•W•T（Ted）Youngs给出的当n≥3时，完全图Kv的亏格的公式：
完全图Kv的亏格＝ （v≥3）        （5）
这个公式是怎么得来的，笔者是没有看到的，但我们可以通过上面的公式（3）或（4＇）式任意图的亏格和完全图的边数与其顶点数的关系式推导出来。推导过程如下：
已经知道顶点数是v的完全图Kv的边数e是
e＝                                     （6）
把（6）式代入（4＇）式n≥ （v≥3）中得
        n≥
         ≥
         ≥
≥ （v≥3）                      （7）
公式（7）与上面的公式（5）地模一样。所以公式（5）和（7）就是顶点数是v的完全图Kv的亏格。
4、赫渥特的地图着色公式
1890年赫渥特早就得到了多阶（任何亏格）曲面上的着色公式，这个公式断言，能嵌入亏格为n的曲面上的所有图的色数是：
γn≤ （n≥1）                    （8）
（8）式中n为曲面的亏格数（也是图的亏格），γn是能嵌入亏格为n的曲面上的所有图的色数。由于当时赫渥特对自已所构造的图——Haewood—图（平面图，其亏格是n＝0）不能进行4—着色，所以就对他的公式附加了成立的条件n≥1。
这个公式更不知当时赫渥特是怎么得来的，但现在是可以通过以上的公式（7）和（7）完全图的亏格推导出来的。推导方法如下：
对完全图Kv的亏格n≥ （v≥3）（公式（5）或（7））在未向上取整之前的形式n≥ 进行变形，得到
    12n≥（v－3）（v－4）
       ≥v2－7v＋12
即
        0≥v2－7v＋12－12n
         ≥v2－7v＋12（1－n）
解这个关于v的一元二次方程
        Δ＝（－7）2－4×1×12（1－n）
　　　　　＝49－48＋48n
          ＝1＋48n
其两个根是
        v1≤ ≤
        v2≤ ≤
由于在v2≤ 中，当n＝0时，v2≤3，已经是包括在v1≤ ≤4之中了；而当n≥1时，v2≤ ≤0，但任何图的色数都只会大于等于1，更不可能小于等于0，所以v2≤ 不符合题意，舍去。该一元二次方程只有一个根v1≤ ，由于图的顶点数一定是整数，所以对v1≤ 还得向下再取整，即有
        v1≤
又因为完全图的色数是与其相同顶点数的图中的最大者，所以又有所有可以嵌入亏格为n的曲面上的图的色数为
        γn≤                            （9）
这公式（9）就是赫渥特的地图着色公式（8），式中的γn仍是亏格为n的曲面（图的亏格也是n）上的图的色数。
5、四色猜测的证明
现在，赫渥特的图Haewood—图已经是可4—着色的（见我的《Haewood—图的4—着色》一文），5—轮构形也是可以4—着色的（见我的《5—轮构形是可4—着色的》一文），那么，赫渥特着色公式（8）（或（9））中的附加条件看来是可以不要了，因为把n＝0代入到该公式中去时，所得到的结果正好是γn≤4，这就是说，任何平面图着色时，其色数一定是小于等于4的。这时我们就可以把（8）式改写成
    γn≤ （n≥0）                   （10）
赫渥特的这个公式是正确的，其中也已包括了平面图（n＝0）在内，这也就使猜测得到了证明是正确的。
                       雷  明
              二○一○年二月十七日于长安
注：此文于二○一○年二月二十三日发表于《数学中国》网站，原名是《不画“图”，不着色，证明四色猜测》。