赫渥特公式是如何得来的 ——四评哈拉里《图论》书中的错误

雷明85639720

赫渥特公式是如何得来的
——四评哈拉里《图论》书中的错误
雷  明
（二○一五年十二月五日）

赫渥特公式是如何得来的，没有看到过赫渥特本人的推导过程（也可能就没有，而是一个经验公式），也没有看到过后人对其推导的过程。是不是这个公式真是一个经验公式，没有推导的过程呢，不是的。本人经过多年的研究，从多阶曲面上图的欧拉公式推导出了赫渥特的地图着色公式。
任何图把不相邻的顶点通过收缩运算，最后都可得到一个顶点数最少的完全图，叫做原图的最小完全同态。这个最小完全同态的顶点数就是原图的色数。
1、设任意图的最小完全同态KV的顶点数是v，因任意图都有3f≤2e（f是面数，e是边数），把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2（1－n）（n是图的亏格）得
    e≤3v－6（1－n）
再把完全图边与顶点的关系e＝v（v－1）/2代入其中得
v（v－1）/2＝3v－6（1－n）
v2－7v＋12（1－n）≤0
解这个一元二次不等式得正根是
v≤（7＋√（1＋48n））/2
由于顶点数必须是整数，所以上式还得向下取整，得
v≤＜（7＋√（1＋48n））/2＞
（式中暂用＜ ＞表示其中的数字向下取整）。因为完全图的γ完＝v，所以又有γ曲≤＜（7＋√（1＋48n））/2＞。这就是赫渥特的多阶曲面上的地图着色公式。
2、因为任意图的最小完全同态KV不一定都是三角剖分（即极大图），所以仍有d平均•v＝2e≥3f的关系。按照哈拉里的思路，把e＝d平均•v /2和f≤d平均•v/3，代入到多阶曲面上图的欧拉公式得
d平均≤6－12（1－n）/v
在完全图中d平均＝v－1，所以又有
        v－1≤6－12（1－n）/v
整理得
        v2－7 v＋12（1－n）≤0
与上面得到的不等式是相同的，其解也应是相同的，即γ曲≤＜（7＋√（1＋48n））/2＞。
3、哈拉里也是用了多阶曲面上图的欧拉公式，但他为什么又得出了p≥［（7＋√（1＋48n））/2］的结果，而没有得到p≤＜（7＋√（1＋48n））/2＞的结果呢（哈拉里这里的p是一个三角剖分图的顶点数）。关键在于他不是从任意图出发，而只是从一个三角剖分图出发的（并不是所有的图都是三角剖分的，如K5）。从而使一个d•v＝2q≤3r的不等式变成了d•p＝2q＝3r的等式。结果使平均度由d平均≤6－12（1－n）/p的不等式变成了一个d平均＝6－12（1－n）/p（等价于哈书中的（12.10）式d平均＝12（n－1）/p＋6）的等式；他没有看到任意图通过收缩后一定可得到一个完全图，且完全图中有非常准确的d＝v－1的关系，而是把一个误差非常大的d≤p－1用来代替一个三角剖分图的平均度d。就使得本来是小于等于0的一元二次不等式p2－7 p＋12（1－n）≤0成了一个大于等于0的一元二次不等式p2－7 p＋12（1－n）≥0（这个不等式哈的书中没有直接写出来），而使得其解由p≤＜（7＋√（1＋48n））/2＞变成了p≥［（7＋√（1＋48n））/2］（即哈书中的（12.12）式）。这哪里是赫渥特的公式嘛。由于这里的p是三角剖分图的顶点数，根本不可能是该图的色数。式中不等号的方向，取整的方向，都正好与赫渥特公式中是相反的。难道这就是11223344和87674938所说的是赫渥特公式的“由来”吗。若按这个结果，平面图的顶点数都是大于等于4的，亏格为1的图的顶点数都是大于等于7的，那么请问，顶点数分别是1、2、3的图（如K1、K2、K3、P3）的亏格该是多少呢，顶点数分别是5、6、6的图（如K5、K6、K3，3）的亏格又该是多少呢。

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

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