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

雷明85639720

再论哈拉里《图论》一书157页中的错误
雷  明
（二○一五年元月一日）

前些日子我在《哈拉里<图论>一书中的错误》一文中已对该书第157页中的《赫渥特地图着色定理》一节中作者哈拉里的错误进行了一些评论，看来还有必要再说得透彻一点。
1、哈拉里说：“段定G是一个三角剖分”，即G是一个极大图。正因为其所用的图不是任意的，而是极大图，这样就出现了平均度d平均乘以顶点数v等于2倍的边数e，也等于3倍的而数f，即d平均&#8226; v＝2e＝3f。如果是任意图，就会是d平均&#8226;v＝2e≥3f。代入到欧拉公式中就不会得到d平均＝12（n－1）/v＋6，而得到的则是d平均≤12（n－1）/v＋6。式中n是图和其可嵌入的曲面的亏格。
d平均≤12（n－1）/v＋6的导出如下：
由于有d平均&#8226;v＝2e≥3f，所以有e＝d平均&#8226;v /2和f≤d平均&#8226;v/3，代入到欧拉公式v－e＋f＝2－2n中得
v－d平均&#8226;v/2＋d平均&#8226;v/3＝2－2n
6v－3d平均&#8226;v＋2d平均&#8226;v≥12－12n
6v－d平均&#8226;v≥12（1－n）
－d平均&#8226;v≥12（1－n）－6v
d平均&#8226;v≤－12（1－n）＋6v
d平均≤12（n－1）/v＋6
紧接着
若图是KV完全图，则一定有d平均＝v－1的关系，把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≤（7＋√（1＋48n））/2
因为这里的v是完全图或图的最小完全同态的顶点数，其必须是整数，所以还要向下取整，则
        v≤＜（7＋√（1＋48n））/2＞
式中的＜ ＞表示其中的数字向下取整。因为图的色数等于其最小完全同态的顶点数，所以也有
        γn＝v最小完全同态≤＜（7＋√（1＋48n））/2＞
这就是赫渥特的地图着色公式。
2、哈拉里在证明中却得到v≥［（7＋√（1＋48n））/2］（式中［ ］其中的数字向上取整），与赫渥特给出的地图着色公式v最小完全同态（γn）≤＜（7＋√（1＋48n））/2＞中所用的不等号的方向和取整的方向正好都是相反的。
哈拉里令［（7＋√（1＋48n））/2］＝H（n），从他得到的公式v≥H（n）看，好象是任意图的顶点数都要大于等于H（n），但的确有K5图和K6图以及K3，3图的顶点数分别是5，6，6，它们都是小于H（1）＝7而不是大于等于H（1）＝7的，而只有K7图以及密度是7的所有图的的顶点数才是大于等于H（1）＝7的。哈拉里的这个公式能说明什么问题呢，什么也不能说明。
若令赫渥特的公式中的＜（7＋√（1＋48n））/2＞＝H（n），则该公式表示的就是任意图的最小完全同态的顶点数v最小完全同态（完全图的最小完全同态的顶点数与该完全图的原顶点数相同），也就是任意图的色数γn一定是小于等于H（n）的。如K5图、K6图、K3，3图、K7图的最小完全同态的顶点数分别是5、6、2和7，其色数分别也是5、6、2和7，它们都是小于等于H（1）＝7的。
3、哈拉里说：“因为γ（Kv）＝v，我们已经找到了一个图亏格等于n而色数等于H（n）。这就证明了H（n）是γ（Sn）的下界。”这种说法是不对的。H（n）只能是亏格为n的图的色数的上界，而不是下界。例如K5图、K6图、K3，3图、K7图的亏格都是n＝1，其色数分别是5、6、2、7，最大只是等于H（1）＝7，而没有一个是大于H（1）＝7的。H（n）只能是γ（Sn）的上界。如果说“H（n）是γ（Sn）的下界”，那么K5图、K6图、K3，3图该怎么着色呢，这些图的顶点数本身就小于H（1）＝7，如何去用大于等于H（1）＝7种的颜色着色，总不能把某些顶点用两种颜色着上吧。这符合着色的原则吗，符合节约的原则吗。
4、哈拉里在得出上面的结论之前就说：“显然，若v＝H（n），我们就有足够多的颜色。”这句话是什么义思呢，让人费解。紧拉着他又说“否则，若v＞H（n），我们以H（n）代” d平均＝12（n－1）/v＋6“中的v，得到不等式d平均＜12（n－1）/H（n）＋6＝H（n）－1。”在进行了一大段令人难以理解的推理之后，得到一个“以此类推，所以G本身是H（n）—可着色的。”的结论，这句话的意思是可以用H（n）种颜色给G来着色，但H（n）并不是G的色数。例如，一个4—圈可以用H（0）＝4种颜色来着色，但H（0）＝4却并不是4—圈的色数，因为4—轮圈的色数是2而不是4。
5、接着哈拉里说：赫渥特地图着色“定理的另一半，其证明是是困难的。但是林格尔和杨斯已经提供了工具。”这个工具就是1978年林格尔和杨斯给出的完全图的亏格公式n（KV）＝［（v－3）（v－4）/12］。
杨斯公式与赫渥特公式尽管表现不同，但它们却是同一个公式的两种不同的表达方式，赫渥特公式是用曲面和图的亏格来表达该图的色数或最小完全同态顶点数的公式，而杨斯公式则是用顶点数来表达相同顶点数的完全图的亏格的公式。两公式是一个互为反函数的关系，是可以相互转换的。
把杨斯公式进行变化得：
n（KV）＝［（v－3）（v－4）/12］
n＝（v－3）（v－4）/12
12n＝v2－7v＋12
v2－7v＋12－12n＝0
v2－7v＋12（1－n）＝0
把赫渥特公式进行变化得：
v最小完全同态（γn）≤＜√（7＋（1＋48n））/2＞
v≤（7＋√（1＋48n））/2
2v≤7＋√（1＋48n）
2v－7≤√（1＋48n）
        4v2－28v＋49≤1＋48n
4v2－28v＋48－48n≤0
v2－7v＋12－12n≤0
v2－7v＋12（1－n）≤0
两个公式变化的结果都是同一个一元二次方程或一元二次不等式，杨斯公式是这个不等式进行因式解解并向上取整的结果，而赫渥特公式则是对该不等式求解的正根向下取整的结果。这个一元二次不式就是我们在上面1中得到的一元二次不等式v2－7v－12（n－1）≤0。这个一元二次不等式也可以从把任意图中边与面的关系3f≤2e和完全图的边与顶点的关系e＝v（v－1）/2代入多阶曲面的欧拉公式v－e＋f＝2－2中得到。请读者自已推导一下。
即然杨斯公式和赫渥特公式是同一个公式的两种不同表达形式，那么用杨斯公式来证明赫渥特公式就不应该了，这也是哈拉里该《图论》一书的错误所在。赫渥特的地图着色公式应该就是直接从欧拉公式去进行推导，直接就得到赫渥特的地图着色公式，根本就不需要进行什么证明了。
6、哈拉里在《图论》书中《赫渥特地图着色定理》一节的最后说：赫渥特的公式γ（Sn）＝＜（7＋√（1＋48n））/2＞（n＞0）式在n＝0时的特殊情形就是4CC。请问，是在什么特殊情形下才是4CC呢。作者在一开始就给赫渥特公式后加了一个限制条件（n＞0），直接就把平面图排斥在外，这难道能是对平面图是否适用于赫渥特公式的证明吗。
从哈拉里的这一节《赫渥特地图着色定理》的“证明”中可以看出，哈拉里在这里的思想是混乱的。既然前面在γ（Sn）≤＜（7＋√（1＋48n））/2＞（n＞0）中已经排除了亏格n＝0，那么后面又说γ（Sn）＝＜（7＋√（1＋48n））/2＞（n＞0）“在n＝0时的特殊情形就是4CC。”这不又等于说该公式同时又适用于亏格n＝0的情况吗。在这里作者哈拉里道底是认为赫渥特的地图着色公式对于亏格n＝0的图是适用还是不适用呢。看来哈拉里也是没有弄明白的。
前面在本节最开头哈拉里已经说过：“希伍德还可以证明，亏格为n的可定向的曲面的色数有一个上界γ（Sn）≤＜（7＋√（1＋48n））/2＞（n＞0）”，但后边又说这就证明了H（n）是γ（Sn）的下界。”这不是前后矛盾了吗。从哈拉里的“证明”中得到的（8）式v≥［（7＋√（1＋48n））/2］看，公式左边是大于右边的，那么所用的取整符号［ ］应认为是向上取整，但他在该用向下取整符号＜ ＞的赫渥特的地图着色公式γ（Sn）≤＜（7＋√（1＋48n））/2＞（n＞0）中也用了向上取整符号［ ］，使之成为了γ（Sn）≤［（7＋√（1＋48n））/2］（n＞0），这也是一个错误。

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

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