公式推导证明四色猜测的三种方法

雷明85639720

公式推导证明四色猜测的三种方法
雷  明
（二○一七年元月三十一日）

1、用平面图中可嵌入的最大完全图的顶点数来证明
已知顶点数v≥3的图都有3f≤2e（f是面数，e是边数）的关系，把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2（1－n）（n是图的亏格）得
    e≤3v－6（1－n）（v≥3）                      （1）
（1）式就是多阶曲面上图中顶点与边的关系。当图是完全图时，应有e＝v（v－1）/2的关系，把e＝v（v－1）/2代入（1）式得
v（v－1）/2＝3v－6（1－n）
v2－7v＋12（1－n）≤0                          （2）
解这个一元二次不等式（2），得其正根是
v≤（7＋√（1＋48n））/2  （v≥3）
由于顶点数v必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞ （v≥3）       （3）
（3）式中暂用＜ ＞表示其中的数字向下取整。（3）式中的v就是可嵌入亏格是n的曲面上的完全图的顶点数。平面图的亏格是0，把n＝0代入（3）式中，得
v≤4                                        （4）
（4）式就是可嵌入亏格为0的平面上的完全图的顶点数。公式（4）也可以直接从平面图的边与顶点的关系式e≤3v－6 （v≥3）得来。把完全图中边与顶点的关系e＝v（v－1）/2代入上式e≤3v－6中 得
v2－7v＋12≤0  （v≥3）                                  （5）
解（5）式这个一元二次不等式得
v1≤4和v2≤3                                                   （6）
由于v2≤3包含于 v1≤4中，所以实际只有一个根
        v1≤4                                        （6＇）
与上面的（4）式完全同。由于完全图着色，所需颜色数就是其顶点数，把（3）式中的顶点数v换成颜色数γ，则（3）式变成
γ≤＜（7＋√（1＋48n））/2＞ （v≥3）       （7）
把n＝0代入（7）式中，得
    γ≤4                                        （8）
（8）式就是平面上完全图的色数，是不大于4的。因为图的色数就是其最小完全同态的顶点数，而任何平面图的最小完全同态也一定是平面完全图，所以（8）式也就是任意平面图的色数公式。因为γ≤4，这也就证明了四色猜测是正确的。
2、用平面（或球面）上不存在五色地图来证明
设在某亏格为n的曲面上有一个γ色的地图，按坎泊的思想，那么就应该存在一个“国数最小的”γ色地图。这个“国数最小的”地图中也就只应有γ个“国家”（这个“国数最小的”地图中的“国家”数γ，实际上就相当于图的最小完全同态的顶点数）。
设这个“国数最小的”地图中的区域数（即“国数”）为f，每一个区域都与别的f－1个区域相邻，每一个区域都有f－1条边界线，f个区域的总共有f（f－1）条边界线。因为每条边界线都是两个区域所共有的，而在这些边界线中，每条边界线都是计算了两次的，所以就有2e＝f（f－1）；又因为地图是一个3—正则图，即每一个顶点都连着3条边（即所谓的“三界点”），所以该地图的总边数也可以写成e＝3v/2，即有2e＝3v，从而有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则得到
f2－7f＋12（1－n）＝0                        （1）
解这个关于“国数最小的”地图中的区域（国家）数f的一元二次方程（1）得正根是
        f＝（7＋√（1＋48n））/2
因为区域数必须是整数，所以上式还得向下取整，得
        f＝＜（7＋√（1＋48n））/2＞                 （2）
式中用＜ ＞表示其中的数字向下取整。又因为f是两两均相邻的“国数最小的”地图的“国数”，即区域数，所以这个“国数最小的”地
图染色时也必须用与其区域数相同的颜色数，所以又有
        γ＝f＝＜（7＋√（1＋48n））/2＞             （3）
这个区域数f只是某一亏格为n的曲面上“国数最小的”地图中的“国数”最大者。若从这个“国数最小的”地图中去掉一条边，或者去掉一个“三界点”顶点及其所连的3条边，该地图中的区域数就都会减少。在这个“国数最小的”地图中，原来是一个区域染了一种颜色，那么现在区域数少了，所用的颜色数也就会减少下来。所以上式还可以再增添上“不等式部分”，即
        γ＝f≤＜（7＋√（1＋48n））/2＞             （4）
（4）式中当曲面的亏格为n＝0时，其两两区域均相邻的区域数和色数都是不大于4的，即γ＝f≤4，说明了平面地图中是不存在五个区域两两均相邻情况的。即平面地图中是不存在五色地图的。（4）式就是平面地图中两两均相邻的区划数，也是就是（平面）地图着色的色数，是小于等于4的。这就证明了地图四色猜测是正确的。
地图中两两均相邻的区域的个数不大于4（即不存在五色地图）还可以直接用平面图的欧拉公式来证明。把把v＝f（f－1）/3和e＝f（f－1）/2代入到平面图的欧拉公式v＋f－e＝2中，则得到
f2－7f＋12＝0                                （5）
解（5）的一元二次方程得两个正根分别是
f＝4和f＝3
均小于5，也说明了平面地图中只能存在3个或4个区域两两相邻，而不存在5个区域两两相邻的情况，即不存在五色地图。
按坎泊的思想，只要能证明平面地图中不存在五色地图，那么地图四色猜测就是成立的。现在已经证明了平面地图中的却不存在五色地图，所以地图四色猜想就是正确的。地图四色猜测相是正确的，那么给地图的对偶图——极大平面图的顶点着色，也就只要四种颜色就够用了。四色猜测是正确的。
3、用赫渥特地图着色公式来证明
顶点数v≥3的图都有3f≤2e（f是面数，e是边数）的关系，把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2（1－n）（n是图的亏格）中得
    e≤3v－6（1－n）（v≥3）                     （1）
注意，这里对图的亏格可是没有任何限限制的。再把完全图边与顶点的关系e＝v（v－1）/2代入（1）式中得
v（v－1）/2＝3v－6（1－n）
v2－7v＋12（1－n）≤0                         （2）
解这个一元二次不等式（2），得其正根是
v≤（7＋√（1＋48n））/2  （v≥3）
由于顶点数v必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞ （v≥3）        （3）
（3）式中暂用＜ ＞表示其中的数字向下取整。这就是可嵌入亏格为n的曲面上的最大完全图的顶点数。因为完全图的色数γ就等于其顶点数v，即有γ完＝v，所以又有多阶曲面上图的色数是
γ图≤＜（7＋√（1＋48n））/2＞ （v≥3）      （4）
（4）式就是赫渥特的多阶曲面上的地图着色公式，它是适用于任何亏格的图的。四色猜测研究的是平面（球面）上的图的着色，把平面（球面）图的亏格等于0代入（4）式中得γ平≤4；这就证明了四色猜测是正确的。
林格尔公式与赫渥特地图着色公式是互为反函数的，是可以相互推导的。林格尔公式n＝〔（v－3）（v－4）/12〕（v≥3）表示的是不同顶点数的完全图的亏格数（这里也暂用方括号〔 〕表示其中的数字向上取整）。它和赫渥特的地图着色公式同样都是上面（2）式中的一元二次不等式的解的一种形式。在（2）式的v2－7v＋12（1－n）≤0中，有两个可变的参数，一是图的顶点数，一是图的亏格。两个参数都可作为自变量，而把另一个作函数求其值。上面赫渥特的地图着色公式就是把图的亏格n作自变量，求某亏格n下的最大完全图的顶点数v值的公式；而林格尔公式则是把图的顶点数v作自变量，求该顶点数是v的完全图的亏格n的。由于某一顶点数的完全图的亏格只可能是一个，所以林格尔公式中只用了等式。这两个公式是互为反函数的，呵以相互推导的。不能用来相互进行证明，否则就成了循环论证。沙特朗在他的《图论导引》一书中，用林格尔公式去证明赫渥特地图着色公式是不合适的。
当时赫渥特是怎么得到他的地图着色公式的，我们不可能知道。但我们在推导该公式的过程中，是没有对亏格附加任何条件的。这种可以经过严密数学推导而得到的结论，是不需要再进行证明的，因为推导过程中每一步都是符合逻辑的。所以用林格尔公式证明赫渥特的地图着色公式，或都反过来又用赫渥特的地图着色公式证明林格尔公式，都是错误的。


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

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

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

,,,,,,,,

雷明85639720

，，，，，

雷明85639720

,,,,,,,,

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，

雷明85639720

，，，，