六论哈拉里对赫渥特着色公式的证明

雷明85639720

六论哈拉里对赫渥特着色公式的证明
雷  明
（二○一五年十二月二十一日）

1、哈拉里证明中有用部分的准备工作：
哈拉里在他的《图论》书中证明赫渥特的多阶曲面上的地图着色公式χ（Sn）≤〔（7＋√（1＋48n））/2〕（n＞0）（注意：这开始就把亏格n＝0的平面（或球面）S0和n＝0平面图排斥在外了。原作式中的〔 〕表示其中的数字向下取整）时，他先对不等式进行了“证明”。他假定G是一个嵌入Sn的三角剖分，所以有d•p＝2q＝3r（式中p、q、和d分别是G的顶点数、边数，面数和平均度。把q和r用p来表示，并代入多阶曲面上图的欧拉公式，解出平均度d得
d＝12（n－1）/p＋6
因为d≤p－1，代入上式得到
        p－1≥12（n－1）/p＋6
由上式解出顶点数p，可以得到正根
p≥（7＋√（1＋48n））/2
因为顶点数p应是正整数，所以还得取整。在这里上式应是向上取整，用符号{ }，得到
p≥{（7＋√（1＋48n））/2}
而哈拉里却用了向下取整的符号[ ]，成了
p≥〔（7＋√（1＋48n））/2〕
这不能不算作一个小小的错误。
上面的这个式子是一个什么意思呢，是乎是可嵌入亏格是n的曲面上图的顶点数公式，但实际上又不是。按该式计算，可嵌入亏格是1的轮胎面上图的顶点数是p≥7，那么请问K5和K6的顶点数分别是5和6，他们的亏格是多少呢；而当亏格是2时，计算结果是p≥9，但的确K8的亏格也是2，顶点数又是8＜9；而当亏格是0时，计算的结果是p≥4，难道顶点数数分别是1、2、和3的K1、K2和K3都不是平面图吗。所以说公式p≥{（7＋√（1＋48n））/2}和 p≥〔（7＋√（1＋48n））/2〕实际上都是一个四不象的式子，说明不了什么问题。在以下的证明中，除了d＝12（n－1）/p＋6用到了之个（实际上仍没有起到作用，可以不用），而这个p≥{（7＋√（1＋48n））/2}或 p≥〔（7＋√（1＋48n））/2〕都没有用上。
2、哈拉里证明中有用部分的内容：
接下来哈拉里进行证明：首先他令H（n）＝〔（7＋√（1＋48n））/2〕，然后说：“我们必须证明用H（n）种颜色来着色G的顶点是足够了。显然，若p＝H（n）我们就有足够多的颜色。否则，若p＞H（n）”然后他以H（n）代替d＝12（n－1）/p＋6中的p，“得到不等式d＜12（n－1）/H（n）＋6＝H（n）－1。……”。
显然，从“令H（n）＝〔（7＋√（1＋48n））/2〕”到“我们必须证明用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是顶点数为p的三角剖分图的顶点平均度，而这里的H（n）－1则是顶点数为n的完全图Kn的平均度，显然H（n）－1与12（n－1）/H（n）＋6是没有什么关系的，是不能用等号连接起来的。）接下来又说为了得到后面的等式“12（n－1）/H（n）＋6＝H（n）－1”，“只要进行通常的代数变换。于是，当p＞H（n）时，有一个顶点v它的度至多等于H（n）－2”，这里说得很不明确。如果当n＝1时，H（n）＝7，当p＝8时，p＞7 ，p＞H（n）。这种情况下，要保持图的亏格还是n＝1不变时，图中至少要有一个顶点只能与其他的7个顶点构成的K7团中的6个相邻，这样才能保证图中的最大团仍是K7，而不会变成K8。所以这个顶点的度最多只能是6＝8－2＝p－2，怎么说是“有一个顶点v它的度至多等于H（n）－2”呢，H（n）－2＝7－2＝5，p－2＝6是不同的。这里好象是有一点错误。
接下来又继续说：“（用一个初等收缩）等同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的图中，有些图的顶点数大于等于H（n）的，而有些图的顶点数则是小于H（n）的。如亏格都是1的图中，K7的顶点数是等于H（n）＝7，而K6和K5的顶点数却是6和5，是小于H（n）＝7的。因为“G本身是H（n）—可着色的”就已说明了G的色数是χ（Sn）≤H（n）的，又因为H（n）＝〔（7＋√（1＋48n））/2〕，所以也有χ（Sn）≤〔（7＋√（1＋48n））/2〕。到此应该说已经证明了赫渥特着色公式在n＞0是正确的了，证明就已经完了。并不是哈拉里前面说的“我们先证不等式”。
3、哈拉里证明中的无用部分：
但接着哈拉里又说：“定理的另外一半，其证明是困难的。但是林格尔和杨斯已经提供了工具。”这另一半可能就是指赫渥特着色公式中的等式了。接下来哈拉里用林格尔和杨斯提供的完全图的亏格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的；亏格为0的图K1、K2、K3和K4的色数分别是1、2、3和4，都是小于等于4的）。证毕。
但最后哈拉里又注明了一句说：“χ（Sn）≤[（7＋√（1＋48n））/2]（n＞0）在n＝0的特殊情形就是4CC。”这恐怕也是因对赫渥特图不可4—着色而不敢直接把n＝0代入其中而得到色数χ（Sn）≤4的原因吧。总之，在这里哈拉里至少是没有说赫渥特公式是不适用于亏格为0的平面图的，虽然他在公式χ（Sn）≤[（7＋√（1＋48n））/2]的后面仍附加了约束条件（n＞0），但这个约束条件是在证明之前加的，而不是经过证明必加不可的。所以我认为这个证明还是不彻底的。
4、评论：
从现在的观点看，赫渥特公式已经可以直接从欧拉公式中推导出来，是没有问题的，是不需要再进行证明的。但哈拉里在证明的那时，还没有人能从欧拉公式中直接推导出赫渥特公式，所以只能这样证明了。但证明一开始就把亏格为0的平面图排斥在外是不应该的，而应是通过证明，确实说明了该公式不适用于亏格是0的平面图时，再附加条件也是不迟的，但这一点他却没有进行证明，仍然看不出公式不适用于亏格为0的平面图的原因。
我认为该公式不适用于亏格0的平面图的原因主要是赫渥特本人对他的图不能4—着色，直到现在也没有专业内数学家对该图实际的进行过4—着色，而对赫渥特能进行4—着色的人正好都不是专业的数学家，而是一些爱好者。所以谁也不能把赫渥特在公式后附加的这个条件去掉。
证明的前一部分，即所谓的先证明不等式的部分，可以说还是可以的，虽有个别地方的错误，但不影响大局。但证明的前期准备工作的确也是没有必要的，因为后面的证明根本就没有用到它。这一部分的证明，实际上就已经证明了赫渥特着色公式的全部，是正确的，不需要再进行后一部分用林格尔公式的证明了。由于哈拉里也不能证明该公式确实是对于亏格0的平面图不成立，所以他最后才说，赫渥特的公式“在n＝0的特殊情形就是4CC”。

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

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

雷明85639720

,,,,,,,,,,

雷明85639720

，，，，，，，，