哈拉里《图论》一书中的错误

雷明85639720

哈拉里《图论》一书中的错误
雷  明
（二○一四年十一月二十日）

赫渥特于1890年提出的多阶曲面上的地图着色公式是：
    γn≤＜（7＋√（1＋48n））/2＞                 （1）
式中的＜ ＞表示其中的数字向下取整。但一直没有看到过该公式是怎么得来的。我通过对拓扑学与图论的研究，发现从多阶曲面上图的欧拉公式可以对其进行推导。也为四色猜测的证明创造了条件。
对于任何图来说，其色数γ都等于其最小完全同态Kα的顶点数α，那么（1）式中的γn就可以用αn来代替，使公式（1）变成
    αn≤＜（7＋√（1＋48n））/2＞                 （2）
由于同一亏格下的各种图的最小完全同态都是不相同的，其顶点数多少也是不同的。这些最小完全同态（也是图）的亏格肯定也是不同的，因为图的最小完全同态的亏格是小于等于原图的亏格的。比如，同是只能嵌入亏格为n＝1的曲面上的图K3，3，K5，K6和K7，其最小完全同态分别是K2，K5，K6和K7，他们的亏格则分别是n＝0和 n＝1。因为图的最小完全同态也是一个完全图，所以只要求出可嵌入某亏格下的最大完全图的顶点数v，就能得到该亏格下的各种图的最小完全同态中顶点数最多的最小完全同态的顶点数α，当然该亏格下的其它图的最小完全同态的顶点数也就一定都是小于等于α的。
    1、赫渥特地图着色公式的推导
    设图的顶点数是v，面数是f，边数是e，亏格数是n。可嵌入某亏格为n的曲面上的图中面与边的关系是3f≤2e，把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2－2n中得
    3v－e≥6－6n
再把完全图中顶点与边的关系e＝v（v－1）/2代入上式中得
        v2－7v＋12（1－n）≤0
解这个二元一次不等式，得正根是
        v≤（7＋√（1＋48n））/2                      （3）
因为图的顶点数一定是整数，所以（3）式还得向下取整，于是有
        v≤＜（7＋√（1＋48n））/2 ＞                 （4）
又由于γn＝αn＝v，所以又有
γn＝αn≤＜（7＋√（1＋48n））/2 ＞           （5）
这就是前面的（1）式和（2）式，就是赫渥特的多阶曲面上的地图着色公式。
2、哈拉里《图论》书中的错误
哈拉里在其著作《图论》中对赫渥特的地图着色公式也有一个“证明”，他首先“假定G是一个三角剖分”，这是一个嵌入到亏格为n的曲面上后，所有的面都是三边形面的图，也即是亏格为n的曲面上的极大图，并不是一个任意的图。这时，则有
    d平均v＝2e＝3f                                （6）
式中d平均是图的平均度。解出e＝d平均v/2和f＝d平均v/3并代入多阶曲面上图的欧拉公式v＋f－e＝2－2n中得
        v＋d平均v/3－d平均v/2＝2－2n
整理后得
d平均＝12（n－1）/v＋6                        （7）
这时，哈拉里说，“因为d平均≤v－1，这就给出不等式
        v－1≥12（n－1）/v＋6
解出v，取正根，我们得到
        v≥［（7＋√（1＋48n））/2］”                 （8）
式中［ ］表示其中的数字向上取整。哈拉里得到的结果（8）式与赫渥特地图着色公式（1）中的不等号与取整的方向都正好是相反的。
为什么会产生这样的情况呢？是因为他首先假定了“G是一个三角剖分”，不是任意的图，因而不具有一般性。
由于G是三角剖分图，所以便产生了（6）式的d平均v＝2e＝3f。若G是任意图时则有2e≥3f的关系，也就有d平均v≥3f的关系。把e＝d平均v/2和f≤d平均v/3代入到欧拉公式中，则得到d平均≤12（n－1）/v＋6而不是d平均＝12（n－1）/v＋6。
已知任何图的色数等于该图的最小完全同态的顶点数，完全同态也是一个完全图，把完全图的平均度d平均＝v－1代入d平均≤12（n－1）/v＋6中，便得到
v－1≤12（n－1）/v＋6
    v2－v－6v≤12（n－1）
    v2－7v－12（n－1）≤0
解这关于v的个一元二次不等式得正根
        v≤（7＋√（1＋48n））/2
因为这里的v是完全图或图的最小完全同态的顶点数，其必须是整数，所以还要向下取整，则
        v≤＜（7＋√（1＋48n））/2＞
这就是前面的公式（4）。因为图的色数等于其最小完全同态的顶点数，所以也有
        γn＝v最小完全同态≤＜（7＋√（1＋48n））/2＞
这就是前面的公式（1）、(2)和（5）,就是赫渥特的地图着色公式。
哈拉里先生对他的公式（8）是这样解释的：“令H（n）为（8）式的右边。我们必须证明用H（n）种颜色来着色G的顶点是足够了。”接下来哈拉里在进行了长篇的论证后说：“因为γ（Kv）＝v,我们已经找到了一个图亏格等于n而色数等于H（n）。这就证明了H（n）是γ（Sn）的下界。证毕。”这里的γ（Sn）是亏格为n的曲面上的色数。
哈拉里在这里的论述也是错误的。比如，用n＝1用（8）式行算出来的结果是v≥7＝H（1），但同样是只可以嵌入到n＝1的曲面上的图K3，3，K5，K6和K7四个图，其色数分别是γ＝2，γ＝5，γ＝6和γ＝7，却都是小于等于7的，没有一个比7大的。这怎么能说“H（n）是γ（Sn）的下界”呢。同样也不可能认为v≥7＝H（n）就是可嵌入亏格为n＝1的曲面上的图的顶点数的“下界”，故然有可嵌入亏格为n＝1的曲面上的图的顶点数是大于7的，但以上四个图的顶点数却分别是6，5，6和7，也都是不大于7的。
许寿椿教授的《图说四色问题》一书中认为赫渥特地图着色公式是可嵌入亏格为n的曲面上的图着色时，“使得有公共边界的区域着不同颜色的最少颜色数”，这也是不对的，而应是“最大着色数”。许教授的这句话只能说对于可嵌入亏格为n的曲面上的最大完全图着色时，按公式（1）计算的结果是“使得有公共边界的区域着不同颜色的最少颜色数”是合适的，但这样的完全图只是极少数的图，并不能代表所有可嵌入亏格为n的曲面上的图。比如，K7图是可嵌入亏格为n＝1的曲面上的最大完全图，7是K7图的最少着色数。虽然大于7种的颜色也可以给密度为ω＝7的、且顶点数大于7的图（图中至少含有一个K7团）着色，但这个大于7的颜色数却不是密度为ω＝7的、但顶点数大于7的图的色数，该图的色数仍是7。
哈拉里在他的“证明”最后说，“（8）式在n＝0时的特殊情形就是4CC。”这个“n＝0时的特殊情形”是什么呢，没有说明。是不是单指K4图和含有K4团作其分子图的图呢。但我们知道在公式（1）中，当n＝0时，计算的结果是γn≤4，这就是四色猜测，即时4CC。
所以只能认为赫渥特的地图着色公式（1）γn≤＜（7＋√（1＋48n））/2＞是可嵌入亏格是n的曲面上的图的色数的上界（最大着色数），而不能是其“下界”，因为任何图的色数的下界都是等于其密度ω的，其密度ω也就是图中最大团Kω的顶点数。
3、任意图的顶点平均度
上面我们在第2个问题中已经得出了一个任意图的平均度的公式
d平均≤12（n－1）/v＋6                        （9）
这个公式也可以用可嵌入亏格为n的曲面上的图的边与顶点的关系e≤3v＋6（n－1）推导出来。即
        d平均＝2e/v≤（6v＋12（n－1））/v
　　　　　　≤6＋12（n－1）/v                        （9）
现在分析如下：
当亏格n＝1时，平均度d平均＝6，d平均与图中的顶点数没有任何关系，平均度曲线是一条d平均等于6的水平直线；当亏格n＜1（n＝0）时，d平均＝6－12/v，平均度d平均随v的增大而增大，d平均＝6－12/v是一个增函数，其上极限是6；当亏格n＞1时，d平均＝6＋12（n－1）/v ，平均度d平均随v的增大而减小，d平均＝6＋12（n－1）/v是一个减函数，其下极限也是6。图若是一个嵌入亏格为n的曲面上的完全图时，d平均＝2（v（v－1）/2）/v＝v－1，v－1≤12（n－1）/v＋6（上面的公式9）；若图是一个嵌入亏格为n的曲面上的极大图时，d平均＝2（3v＋6（n－1））/v＝6＋12（n－1）/v，这就是上面的公式（9）中的等式。

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

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