从求图的亏格到四色猜测的证明

雷明85639720

从求图的亏格到四色猜测的证明
雷  明
（二○一四年十一月二十四日）

所谓图的亏格就是一个图所能嵌入的曲面的最小亏格。而曲面的亏格则是球面上所接环柄的个数。一个图可以嵌入到不同的多个亏格的曲面之中，即把图画在这些曲面中时，图中在顶点以外再没有边与边相交叉的情况。这些曲面中亏格最小的一个曲面的亏格就是该图的亏格。如果把图画在某亏格的曲面上后，图中出现了在顶点以外有边与边相交叉的情况时，该图就不能嵌入到该亏格的曲面中去。
1、多阶曲面上的图的欧拉公式
已经证明是正确的多阶曲面上的图的欧拉公式是
v＋f－e＝2＋2n                               （1）
式中v、f、e、n分别是图的顶点数、面数、边数和亏格数。多阶曲面上的图的欧拉公式的证明见范益政等翻译的《图论导引》。
把该多阶曲面上的图的欧拉公式变形就可以求出任何图的亏格。
2、若在知道图的顶点数、面数和边数的情况下，可以用
    n＝（e－v－f＋2）/2                          （2）
求出其亏格。如：可嵌入到亏格是1的曲面上的K7图的v＝7，f＝14，e＝21，代入（2）式得n＝（21－7－14＋2）/2＝1；K5图v＝5，f＝5，e＝10，代入（2）式得n＝（10－5－5＋2）/2＝1；K3，3图v＝6，f＝3，e＝9，代入（2）式得n＝（9－6－3＋2）/2＝1；可嵌入亏格为0的曲面上的K4图的v＝4，f＝4，e＝6，代入（2）式得n＝（6－4－4＋2）/2＝0；K3图的v＝3，f＝2，e＝3，代入（2）式得n＝（3－3－2＋2）/2＝0；5—轮的v＝6，f＝6，e＝10，代入（2）式得n＝（10－6－6＋2）/2＝0；K2图的v＝2，f＝1，e＝1，代入（2）式得n＝（1－2－1＋2）/2＝0； K1图的v＝1，f＝1，e＝0，代入（2）式得n＝（0－1－1＋2）/2＝0；等等。
3、若当知道图的顶点数和面数的情况下，可以用
n≥〔〈1＋（e－3v）/6〉〕（v≥3）                 （3）
求出其亏格。式中〈 〉表示其中的数字取绝对值，〔　〕表示其中的数字向上取整。现推导如下：
由于任何图中都存在3f≤2e的关系，把f≤2e/3代入多阶曲面上的图的欧拉公式（1）v＋f－e＝2＋2n中得
    v＋2e/3－e≥2－2n
整理并变形得
        n≥（e－3v）/6＋1
由于n是正整数，所以不但要取绝对值，还得再向上取整得
        n≥〔〈（e－3v）/6＋1〉〕（v≥3）                  （3）
这就是（3）式。现仍以以上几个图为例：K7图的亏格是n≥〔〈（21－3×7）/6＋1〉〕＝1；K5图的亏格是n≥〔〈（10－3×5）/6＋1〉〕＝1；K3，3图的亏格n≥〔〈（9－3×6）/6＋1〉〕＝〔〈－9/6＋1〉〕＝〔〈－3/2＋1〉〕＝〔〈－1/2〉〕＝〔1/2〕＝1。K4图的亏格n≥〔〈（6－3×4）/6＋1〉〕＝0；K3图的亏格n≥〔〈（3－3×3）/6＋1〉〕＝0。这都是正确的。唯只有K2图和K1图以及圈、轮、道路或树，按公式（3）计算的亏格却不是0而是1，所以公式是有（v≥3）的条件限制的。如果把公式（3）中的向上取整改成向下取整，则
    n≥＜〈（e－3v）/6＋1〉＞（v≤2）             （3＇）
式中＜　＞表示其中的数字向下取整。把K2图和K2图的参数代入公式（3＇）中，则K2图的亏格n≥＜〈（1－3×2）/6＋1〉＞＝＜〈－5/6＋1〉＞＝＜〈1/6〉＞＝0；K1图的亏格n≥＜〈（0－3×1）/6＋1〉＞＝＜〈－3/6＋1〉＞＝＜〈1/2〉＞＝0。把圈、轮、道路或树的参数代入（3＇）中，则其亏格也都是0了。如5—轮的亏格是n≥＜〈（10－3×5）/6＋1〉＞＝＜〈－5/6＋1〉＞＝＜〈1/6〉＞＝0等。
4、当只知道图的顶点数的情况下，可以用
    n≥〔（v－3）（v－4）/12〕（v≥3）              （4）
求出完全图的亏格。推导如下：
把任意图中顶点与边的关系e≤v（v－1）/2代入以上（3）式中得
    n≥〔（v（v－1）/2－3v）/6＋1〕
变形整理后得
        n≥〔（v－3）（v－4）/12〕（v≥3）               （4）
（4）式说明了某完全图的亏格一定是n＝〔（v－3）（v－4）/12〕（v≥3），它一定是能够嵌入到亏格为n≥〔（v－3）（v－4）/12〕（v≥3）的曲面上去的。例如K7图的顶点数是v＝7，亏格则是n＝〔（v－3）（v－4）/12〕＝〔（7－3）（7－4）/12〕＝〔12/12〕＝1，同样K5图的顶点数是v＝5，亏格则是n＝〔（v－3）（v－4）/12〕＝〔（5－3）（5－4）/12〕＝〔6/12〕＝1，二图均可嵌入亏格大于等于1的曲面上；又如K4图的顶点数是v＝4，亏格则是n＝〔（v－3）（v－4）/12〕＝〔（4－3）（4－4）/12〕＝〔0/12〕＝0，同样K3图的顶点数是v＝3，亏格则是n＝〔（v－3）（v－4）/12〕＝〔（3－3）（3－4）/12〕＝〔0/12〕＝0，同样的，二图均是可嵌入亏格大于等于0的曲面上。
     同样的，完全图K2和K2不包括在（4）式中的，若把（4）式向上取整也改为向下取整，则有
        n≥＜（v－3）（v－4）/12＞（v≤2）            
这时把K2图和K2图的参数代入公式（4＇）中，两图的亏格都是0。如K2图的亏格是n＝＜（v－3）（v－4）/12＞＝＜（2－3）（2－4）/12＞＝＜（－1）（－2）/12＞＝＜（－1）（－2）/12＞＝＜2/12＞＝0
5、三个计算图的亏格的公式的比较
一般的图，除了平面图（亏格为0）能直接看出面数f是多少外，其它的图是无法看出其面数的，而只能看出其顶点数v和边数e。但平面图一般也不需要求其亏格，所以说式（1）是没有多大用处的；式（2）的用处是最大的，可以说对所有的已知其顶点数v与边数e的图，都可以求出其亏格n；而式（3）只是对于完全图有用，但如果知道已知顶点数的图是完全图，那么也就相当于知道其边数了，用公式（2）同样也是可以求出其亏格的。所以说式（2）的用处是最大的。
6、赫渥特地图着色公式的推导与四色猜测的证明
以上的三个公式，分别是一步一步的把f≤2e/3和e≤v（v－1）/2代入到多阶曲面上的图的欧拉公式而得到的，把（4）式在向上取整前的式子变形后就可得到
　　v2－7v＋12（1－n）≤0
解这个关于顶点数v的一元二次不等式，得正根是
    v≤（7＋√（1＋48n））/2                     
由于顶点数是正整数，所以该式还得向下取整得
        v≤＜（7＋√（1＋48n））/2＞                  （4）
因（4）式是由完全图的亏格公式推导出来的，所以这里的v应是完全图的顶点数。由于图的最小完全同态也是完全图，所以（4）式中的v也应是图的最小完全同态的顶点数。而图的最小完全同态的顶点数就是图的色数，所以又有
        γn≤＜（7＋√（1＋48n））/2＞                （5）
这就是赫渥特的地图着色公式（若同时把f≤2e/3和e≤v（v－1）/2直接代入到多阶曲面上的图的欧拉公式中也可以直接得到这个公式）。（5）式中当n＝0时，γn≤4，这也就证明了四色猜测是正确的。
    7、赫渥特地图着色公式的又一推导方法
一个可以嵌入到亏格为n的曲面上的图的边数与顶点数的关系是
e≤3v＋6（n－1），完全图的边与顶点数的关系是e＝v（v－1）/2，该二者的关系又是
        v（v－1）/2≤3v＋6（n－1）
整理并解出v得到
         v≤＜（7＋√（1＋48n））/2＞                 （4）
和
        γn≤＜（7＋√（1＋48n））/2＞                 （5）
这与上面的（4）式与（5）式是完全相同的。这个方法实质上与上面的方法也是相同的，因为e≤3v－6（n－1）本身就是把f≤2e/3代入到多阶曲面上的图的欧拉公式后所得的结果。

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

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