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

雷明85639720

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

哈拉里在书中证明赫渥特公式χ（Sn）≤＜（7＋√（1＋48n））/2＞（n＞0）时，在得到了错误的p≥＜（7＋√（1＋48n））/2＞（即哈书中的（12.12）式，见我的《三评》与《四评》，网址分别是：    和    ）后，接着又说：“令H（n）为（12.12）的右边。我们必须证明用H（n）种颜色来着色G的顶点是足够了。显然，若p＝H（n）我们就有足够多的颜色。否则，若p＞H（n），我们以H（n）代（12.10）（（12.10）式为d＝12（n－1）/p＋6，——雷明注）中的p，得到不等式d＜12（n－1）/H（n）＋6＝H（n）－1   （12.13）……”。
显然，这“令H（n）为……着色G的顶点是足够了”，这是提出了任务。后面的“显然，若p＝H（n）……”是在解决问题。但p＞H（n）时，代入到d＝12（n－1）/p＋6（（12.10）式）中去时，的确是可以得到得到d＜12（n－1）/H（n）＋6，而12（n－1）/H（n）＋6又如何能与H（n）－1相等呢，莫名奇妙，不知道是什么意思（前面的d是三角剖分图的顶点平均度，而这里的H（n）－1却是顶点数为H（n）的完全图Kn的平均度，这怎么能用等号连接起不呢？）。接下来又说“为了得到后面的等式（可能是指上式中的“＝H（n）－1”吧——雷明注）只要进行通常的代数变换。于是，当p＞H（n）时，有一个顶点v它的度至多等于H（n）－2。”当n＝1时，H（n）＝7，当p＝8时，p＞7＝H（n），要保持图的亏格还是n＝1不变时，图中至少要有一个顶点只与其他的7个顶点中的6个相邻，这样才能保证图中的最大团仍是K7，而这个顶点的度至只能是6＝8－2＝p－2，怎么说是“有一个顶点v它的度至多等于H（n）－2”呢，这里好象是有一点错误。
接下来又继续说：“（用一个初等收缩）等同v和它的任何一个邻接的顶点得到一个新图G＇。若p＇＝p－1＝H（n），则G＇可用H（n）种产色着色。若p＇＞H（n），重复得上面的论证，最后总会得到一个H（n）—可着色图。于是容易看出，这个图的一个H（n）—着色导出前一个图一个用H（n）种颜色的着色。以此类推，所以G本身是H（n）—可着色的。”这个证明好象还可以说得过去。
上面已经证明了n＞0的情况下，且顶点数p≥H（n）的图都是可H（n）—着色的。那么不言而喻，当p＜H（n）的图，也一定是能够可H（n）—着色的，因为其顶点数比可用的颜色数H（n）还要小，所以其色数只是小于H（n）而已。到此应该说证明就已经完了，但接着哈拉里又说：
“定理的另外一半，其证明是困难的。但是林格尔和杨斯已经提供了工具。”接下来就用林格尔和杨斯提供的完全图的亏格n（KV）＝［（n－3）（n－4）/12］进行了一番的推导，最后仍得到p＝＜（7＋√（1＋48n））/2＞。实际上，任意完全图的亏格公式n（KV）＝［（n－3）（n－4）/12］与某亏格下可嵌入的最大完全图的顶点数公式v（KV）＝＜（7＋√（1＋48n））/2＞是同一个公式的两种不同表现形式，两式是互相可以导出来的。我认为这一部分证明是完全可以不要的。
哈拉里最后说：“因为χ（KP）＝p，我们已经找到了一个图亏格等于n而色数等于H（n）。这就证明了H（n）是χ（SP）的下界（这一点又说错了，不是“下界”而是“上界”。因为亏格为n的图的色数都是小于等于H（n）的，最大的色数只是H（n），如亏格为n＝1的图K5、K6、K7和K3，3的色数分别是5、6、7和2，都是小于等于7的）。证毕。
但最后哈拉里又注明了一句说：“χ（Sn）≤＜（7＋√（1＋48n））/2＞（n＞0）在n＝0的特殊情形就是4CC。”这恐怕也是因对赫渥特图不可4—着色而不敢直接把n＝0代入其中而得到色数χ（Sn）≤4的原因吧。总之，在这里哈拉里至少是没有说赫渥特公式是不适用于亏格为0的平面图的，虽然他在公式χ（Sn）≤＜（7＋√（1＋48n））/2＞的后面仍附加了约束条件（n＞0）。

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

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