二○○九年我与许寿椿教授的几次通信（一）

雷明85639720

二○○九年我与许寿椿教授的几次通信（一）
雷  明
（二○一七年九月二十四日）

许寿椿教授的《图说四色问题》一书中的错误
——与许教授及何宗光先生共同商讨
雷  明
（二○○八年十二月二十日）

我在网上与浙江科技工程学校的何宗光先生讨论四色问题时，我提出了观点：Heawood对Kempe的否定是错误的，Heawood的图是能够4—着色的。也正是因为Heawood对他自已的图不能进行4—着色，他才匆匆的“证明”出所谓的“五色定理”。何先生不同意我的观点，他认为“这其实是你对Heawood证明的误解，Heawood反例图的作用仅仅是揭示了Kempe的证明有漏洞，并不是说这个图不能用四种颜色着色。（请参看许寿椿所著的“图说四色问题”一书）”。
我按何先生的提示，购到了一本《图说四色问题》，仔细的看了两遍，感到的确不错，是一个很好的科普读物。说它很好，主要是它很通俗，容易看懂，而且是图文并茂，色彩夺目，纸张质量也好，人看了不厌，更重要的是国内多少年来没有出过这样的在图论四色问题方面的专著。但是书中也的确错误太多了，有些是编版印刷错误或原搞笔误，可有些就是明鲜的错误。
1、该书研究的对象主要是对极大平面图的4着色：
该书主要是研究如何用四种颜色、并通过计算机去对极大图进行着色，以及研究各种极大图的4—着色总数的，还没有涉及如何去解决（证明）四色猜测的问题。这里我顺便说一下，机器是不可能进行证明的，它只能是一步不差的按照人所编好的程序给图去着色，所以它只能叫做对猜测的验证。如果人把程序编错了，它也就只能着错，丝毫不会去进行纠正的。如果人能把证明四色猜测的程序编出来，那还要计算机去“证明”干什么呢。如果人能编出来证明的程序，也就说明人能对猜测进行证明，何必要计算机再去证明呢。所谓计算机的证明实际上还是按人编出的着色程序对一个个的图去进行着色，进行验证。现在要问，无穷无尽的图，人是无法着色完的，同样计算机工作再快，也是无法着色完的。猜测还是不能被证明是正确还是错误。笔者通过二十多年的研究，证明人工可以不去对任何一个图进行着色，就能完成对猜测的证明。关于这一方面的问题，请见笔者在网上发表的《图论法证明四色猜测》一文。该文的主要思想及证明过程已在陕西省数学会一九九四年的年会上作过学术报告，地点是在延安大学。猜测说的是任何平面图着色时最多四种颜色就够用了，而该书对极大图着色时，首先是确定了要用四种颜色，使得本来可以用三种颜色着色的图（其色数是3），最后也都用了四种颜色，这是与猜测和图的色数本来意义不相符合的。
许教授在《代前言》中说他在看到2005年网络对“世界最迷人的数学难题”进行评选的结果中，四色问题排为第二名后所说，“看到有这许多数学爱好者，是激励作者抓紧写出这本书的动因之一”。所以可能是由于时间紧，未能很好校对的原因，书中除了印刷错误或者是原稿笔误外，主要有以下几个大的错误。
2、如何正确叙述p—阶定向曲面上的地图着色的Heawood公式：
笔者一共在两个地方看到过Heawood的p—阶定向曲面上的地图着色色数的公式。头一次是在《图论的例和反例》一书，其中是这样说的：“K7能嵌入圆环面的事实可以从Heawood的地图着色定理推出，这个定理断言能嵌入亏格为n的面的所有图中的最大色数是［（7＋√（1＋48n）/ 2］，对n≥0（Ringel和Youngs 1968）”。第二次就是在许教授的《图说四色问题》一书中，书中说：“带有p个柄环的曲面叫做p阶可定向曲面。对p阶可定向曲面上的地图着色，希伍德给出了所需颜色数Mp的如下公式：
Mp＝［7/2＋1/2（1＋48p）］，
此式称为希伍德公式。式中Mp是对p阶可定向曲面上的地图着色时，使得有公共边界的区域着不同颜色的最少颜色数；式中方括号表示取整数部分。这个色式是希伍德的一种猜测。他指出：球面，其柄环为零，即p＝0，此时Mp＝4，这就是四色定理。按照希伍德的上述公式对在轮胎（p＝1）上地图着色，要使其有共边界的区域着不同颜色，需要7（Mp＝7）种颜色。同理，带有两个环柄的曲面是8字型面包圈，而其着色需要8种颜色；带有三个环柄的曲面着色需要9种颜色。希伍德仅仅证明了公式在几种简单情况下是成立的。”
以上两种叙述中的亏格n和阶数p，实际上是一回事，只是叫法不同而已。都是曲面中环圈的个数。笔者认为对于Heawood公式的这两种叙述方法，《图论的例和反例》一书中的叙述较为确切，正确。该公式的值Mp应是亏格为n（或柄环数为p，阶数为p）的曲面上的地图着色所需最多的颜色数，而不是最少的颜色数。否则当n（或p）＝0时，Mp＝4，就成了任何球面上或平面上的地图（或平面图）着色时最少得用4种颜色，这就与地图或平面图的四色猜测就有了矛盾。猜测说的是任何地图或平面图着色时最多4种颜色就够用了。另外，有些地图或平面图的色数的却是小于4的，这算不算是球面上或平面上的地图（或平面图）呢，如果象《图说四色问题》一书中所说的那样，Mp是p—阶曲面上地图着色时所需最少的颜色数，那么K5和K6或者说有五个区划而两两均相邻的地图或有六个区划而两两均相邻的地图就是属于亏格或柄环数是0（或是0阶）的曲面上的地图，这的确是错的。因为K5和K6的确是非平面图，不可能嵌入球面或平面上，而球面或平面上的地图确实也不存在五个区划两两相邻和六个区划两两相邻的情况。如果说Mp是p—阶曲面上地图着色时所需最多的颜色数，那么以上的几个矛盾问题就顺理成章的解决了。
另外，阶数p大的曲面上的地图的Mp一定是包含着阶数p小的曲面上的地图的。比如，含有K7，K6，K5的图能嵌入p＝1的曲面（Mp＝7），而含有K3，K2，K1的图也能嵌入p＝1的曲面，但含有K7，K6，K5的图却不能嵌入p＝0（Mp＝4）的曲面。K3，3及含有K3，3的图的色数是2，它不能嵌入p＝0的曲面，但能嵌入p＝1的曲面。至于K4及含有K4团的图有两种情况，一种情况是当图是平面图时，是能够嵌入到p＝0的曲面的，色数也一定是4；而另一种情况是当图不是平面图时，是不能嵌入到p＝0的曲面上的，而只能嵌入到p＝1的曲面，这时的色数可能是5，也可能是6（这一点可见我的《图论法证明四色猜测》的论文）。密度为4的图是一个由平面图向非平面图过渡的图。
许教授在第12页中还说：书中的图1.8用7种颜色着色的轮胎面上的7个相互相邻的面的例图“说明环面着色至少要7种颜色才能使有公共边界的区域着不同颜色”。同样的原因，许教授在第12页中说的：书中的图1.8用7种颜色着色的轮胎面上的7个相互相邻的面的例图“说明环面着色至少要7种颜色才能使有公共边界的区域着不同颜色”这也是错误的。
     3、高阶曲面上Heawood公式是否都是正确的：
Heawood公式只有在p＝0和p＝1时才是整数，其他任何情况下均是非整数，而且p＝0时，Mp＝4，p＝1时，Mp＝7。的确色数Mp＝4的图（如K4）和色数Mp＝7的图（如K7）正好分别是能嵌入阶为p＝0和p＝1的曲面上的图，且Mp＝4和Mp＝7是阶为p＝0和p＝1的曲面上的最大色数。Heawood的公式是乎是根据这样的两个事实拼凑起来的，而不是根据一般情况而推导出来的。当p＝0时，公式中根号里面正好是1，开方后还是1，使得公式的值正好是4，而当p＝1时，公式中根号里面正好是49，开方后正好就是7，使得公式的值也正好是7，而p为别的值时公式的值都不是整数。这个公式对亏格p为任何值的曲面都适用，还有待于研究。如果说这个公式是经过严密的数学推导出来的，那么当然四色猜测也就是正确的了。
教授书中说：“非定向曲面上的与四色问题对应的问题已经园满地解决了；定向曲面上除去最初的平面（球面）上的四色问题外，其他高阶曲面（有一个或多个环柄的球面）上的与四色问题对应的问题也都完满地解决了。唯独看起来是最简单、最低级、最初始的四色问题，没有获得完满解决。用那些解决高阶曲面获得成功的好方法，都无法对付这个最简单、最低级、最初始的四色问题。”曲面的“阶”是无限之多的，都验证完了吗，没有，也不可能，那么，Heawood公式对于任意亏格的曲面就不一定都能成立。正如用着色的方法验证四色猜测那样，你验证的图再多，且都是只用四种颜色就够了，也不能证明四色猜测就得到证明是正确的一样，因为你不可能把所有的图都着完。1976年Appel所谓的用电子计算机证明了四色猜测也是这样。如果说通过逻辑推导，严密的数学证明，证明了这个公式对于任何亏格的曲面都是正确的话，那么，对于亏格为0的曲面（即平面或球面）也应该是正确的，四色猜测也就得到了证明，就不存在“唯独”它“没有获得完满解决”的问题。所以我认为：（1）Heawood的着色公式是否是经过了严密的数学导而来的，它对于任意亏格的曲面是否都正确，还是有待研究的问题；（2）不能笼统的说非定向曲面和定向曲面上与四色问题对应的问题都得到了解决，只能说对一部分高阶曲面进行了验证，Heawood着色公式是正确的；（3）由亏格为0的平面（球面）和亏格为1的轮胎曲面而得来的Heawood公式不能说对于别的曲面都正确，而唯独对于平面（球面）就不正确了。
4、Kempe对四色猜测的证明中的漏洞在哪里？：
许教授在第一章中写道：“……1879年，律师兼数学家肯普（Kempe）发表了他的一个证明［7］。……，不料11年后，1890年，在牛津大学就读的青年希伍德（Heawood），用一个反例图（图1.3        ）指出肯普证明中有漏洞［11］。希伍德反例图就成为图论里第一个最著名的例图”（引文中上标和图号是许教授书中所引用的文献号和《图说四色问题》一书中的图号——本文笔者注）。接着下面又说“特别需要说明一下，希伍德反例图的作用仅仅是揭示了肯普证明中有漏洞，并不是说这个图不能用四种颜色着色（同样的说法在书的第17页里也有：‘希伍德反例图’，‘……是用来揭示肯普’……‘证明中的差错’。”我认为这种提法是不恰当的。
书中没有说明Kempe的“漏洞”到底在什么地方，只就这么简单的说了一下Kempe有“漏洞”（所有的资料中都只是这么说了一下，许教授也是同样这样说了一下）。说有漏洞，却又没有指出漏洞在那里、并如何进行补救，这是不能叫人心服口服的。我认为Kempe的漏洞就是他对他的图不能进行4—着色，所以才否定了Kempe的证明。要不为什么一百多年来一直把Heawood的图看做图论里的一个反例图呢。至于Heawood的图能够4—着色，那只是现在的事，至少Heawood本人那时是不能4—着色的。书中前面说“希伍德（Heawood），用一个反例图（图1.3）指出肯普证明中有漏洞”，后面又说“并不是说这个图不能用四种颜色着色”，前后就有了矛盾。前面说的Heawood用一个图指出Kempe的证明中有“漏洞”，很明显，指的就是Heawood对这个图不能4—着色，除此不能再作任何解释，因为Kempe证明了任何地图或平面图都可以4—着色；后面又说“不是说这个图不能用四种颜色着色”，这就当然成为前后矛盾的了。“并不是说这个图不能用四种颜色着色”这句话只能说明是许教授现在的看法，因为Heawood的图的却是可以4—着色的。一百多年前的Heawood却不是这样看的，而是认为他的图是不能4—着色的，1972年Saaty也认为是不能4—着色的，还有1988年4月印刷的翻译本《图论的例和反例》一书的作者和译者等，同样也仍认为Heawood的图是不能4—着色的，所以在该书中仍把Heawood的图叫做反例图。笔者认为，也就是因为这个原因，Heawood才匆匆得出了一个所谓的“五色定理”。试问，如果再有人对某些图连用五种颜色都不能着色时，是不是还要再来一个六色、七色，甚至是更多色的定理呢，那还要花那么大的劲去证明四色猜测干什么呢。
许教授在书中一方面把Heawood的图称为“图论里第一个最著名的”反例图，一方面又说“并不是说这个图不能用四种颜色着色”，这不是相互矛盾的吗。四色问题的“反例图”，还能“用四种颜色着色”吗。是反例图就一定不能进行4—着色，能4—着色的图也不能叫做反例图。既已得到了Heawood的图的4—着色，就不应再习惯的称其为“反例图”了。
许教授在书中还说：“希伍德在指出肯普的差错后，没有完全否定、抛弃肯普的成果。他借用肯普的方法，给出五色定理的证明。这个证明简短、易懂，其正确性得到公认。”叫我说，给每个顶点各用一种颜色那不更“简短、易懂”吗。所以笔者认为Heawood所谓“五色定理”的证明完全是为了他的图他自已不能4—着色而抛出的。他的所谓“证明”，也并没有什么新的方法，仍然用的是Kempe所创造的“颜色交换”的方法，并没有见他与Kempe有什么不同的地方。
Kempe的证明有没有漏洞呢，不能说没有。在《图论的例和反例》一书中有这样的话：Kempe自“认为他用下面的方法已经证明了猜测，即用‘证明’：如果一个顶点V与五个其它用四种颜色着色的顶点邻接，那么总能空出诸颜色之一用来给V着色。他用了邻接顶点交错着色的道路（尽管在他的原始论文中一切都是用了地图的术语来说明的），交换这些道路上各顶点的颜色，便可空出一种颜色给V。”从这里可以看出，Kempe本人自认为他已证明了猜测是正确的。笔者认为他这里只是说明了“顶点V与五个其它用四种颜色着色的顶点邻接”的情况，而没有说明顶点V与五个以上其它用四种颜色着色的顶点邻接的情况。这就是Kempe的漏洞。在这种情况下的V能否可以着上已用过的四种颜色之一呢，笔者认为是可以的。因为在这种情况下，也一定包函着多个“顶点V与五个其它用四种颜色着色的顶点邻接”的情况。“顶点V与五个其它用四种颜色着色的顶点邻接”的情况，可以空出颜色给V，那么，在顶点V与五个以上其它用四种颜色着色的顶点邻接的情况下，也一定可空出已用过的颜色之一给V着上。这就算是笔者对Kempe证明的一点补充吧。
Heawood的图的4—着色，其实是很容易的，只是Heawood没有掌握象他所构造的这一类图的着色方法而已。Heawood的图的4—着色，笔者早已于一九八九年着色成功，并于一九九二年三月八日在陕西省数学会第七次代表大会暨学术交流会上作过学术报告，地点是在中国人民解放军西安空军工程学院。关于Heawood的图的4—着色，请见笔者在网上发表的《Heawood—图的4—着色》、《Heawood—图的分析》和《Heawood着色失败的原因》三篇论文。
Heawood的图的确是有一定的代表性，着色比较难一些，但只要掌握了这类图的着色方法，却也很容易。Heawood的图不能4—着色的说法已统治了一百多年，一直阻止着四色猜测的证明，所以只有突破了对该图的4—着色，才能重新看到猜测是可以手工证明的希望。所以许教授不应该对那位“耗费了十余年业余时间”，证明了Heawood的图是能够4—着色的已退休的高级工程师的工作进行惋惜，而应该看到他也是一个把一个错误的历史事实颠倒过来的有刻若攻关毅力的人。本来是可以4—着色的一个图，一百多年来却一直被人们认为是不可4—着色的，这不是一个错误的历史事实吗。还有书中说的那个记者的传扬也是应该的，不是“后果诚堪可虑”，而应是看到“四色猜测的手工证明大有希望”。如果许教授只从“这样一次平常的读报”，“成为剌激、推动”你“动笔写这本小书的一个”“缘由”，那就是错误的了。更不应在第8页中，在讲到四色爱好者寄给专业杂志社的稿件时说：“这些稿件”，“……它们大都被抛之一旁，无人理睬。”这是一种错误的作法。不见得“外行”就没有可取之处，Kempe不就是一个律师出身的人吗，但却在四色问题的证明中有不可可磨灭的功勋。
5、书中所画加德纳图和它的对偶图的错误：
许教授《图说四色问题》一书中加德纳图和它的对偶图是有错误的，书中所画的两个图根本就不是互为对偶的图。这是我写这一文章的主要目的。
书中所画加德纳图和它的对偶图如图1、图2所示。图1中的区域序号是笔者依据图2中的相应顶点的编号所增加的。

（1）图1中的《图说四色问题》一书中图1.11的加德纳图，有几个错误的地方：㈠ 这是加德纳人为设计的一张“地图”，应是一个3—正则图，即每个顶点的度（度即许教授所说的“次”）都是3的图，但图中却出现了一个4度的顶点，如图中的a点，可是在其对偶图图2中却没有相应的4—边形面。依据图2中的顶点相邻情况，笔者认为应将区域99的边界中的a—b段向左外推，移到图中的虚线位置才正确。㈡ 该图包括无限面明明共有113个区域（区域也就是图论中的面），而许教授却说“加德纳的地图有110个区域”。这是其错误之一。图1中的区域73和79在《图说四色问题》一书中的原图中是没有的，这两个面是笔者按其对偶图图2中的顶点排序规律而增加的，所以在其序号数字外画了一个圆圈。如果加上这两个面，图1中就有115个面。

㈢ 许教授说“标记Ⅰ的区域（图中着绿色的区域）仅仅和三个区域相邻。它的着色被三个邻域唯一确定，故该区域可删去而不影响结果。”可是图中明明和这个标记Ⅰ的区域（即图中笔者所标注的109号区域）相邻的区域不是三个，而是有四个。这个区域Ⅰ（即109号区域）也是不能随便删去的。这是其错误之二。㈣ 由于许教授删去了标记为Ⅰ的109号区域，所以在后面他所“实际处理的有109个区域”的地图的对偶图极大图g109的着色将都是错误的。当然了，如果说极大的g109图不是加德纳图的对偶图，那么后面的处理当然有可能是正确的。
（2）图2中的《图说四色问题》一书中图3.6的加德纳图的对偶图g109，也有几个地方有错误：这个图本身作为一个极大图，是没有错的，但作为图1的对偶图来说，却有好几个大的错误。㈠ 图中多了73和79两个顶点，因为图1中没有这两个区域。㈡ 图中还少了一个顶点，即图1中标有Ⅰ字样的109号区域所对应的顶点。㈢ 图1中不存在两个区域有两条以上的共同边界，但这里在顶点90和顶点108间却有两条平行边。有一条是多余的。㈣ 图1中不存在那个区域与多于10个以上的区域相邻的情况，而这里却有顶点90和顶点100的度分别是14（如果除去顶点90与顶点108之间的两条平行边之一，顶点90的度也还有13）和10。顶点90在图1中对应的面90只与7个面相邻，而顶点100在图1中对应的面100也只与6个面相邻，不知道这两个顶点的度有那么大是怎么得来的。㈤ 在图1中许教授删去了一个标有Ⅰ字样的109号区域，那么在图2中的109号顶点就应该是图1中的无限面所对应的顶点。但在图1中与无限面相邻的区域有7个，而在其“对偶的”图2中的顶点109的度却是6，这也不知是为什么。㈥ 图1的区域数是113（或者115）个，而这里的总顶点数却只有109个。
也不知是什么原因。
（3）从以上两点分析可以看出，图1和图2根本就不是一对互对偶图，哪一个是对的，笔者也弄不清楚。
① 如果图1是对的，则其对偶图就应是图3或图4。图3是当图1中没有区域73和79情况下的对偶图，而图4则是当图1中有区域73和79情况下的对偶图。

② 如果说图2是对的，那么对应的加德纳图就应是图5那样（如图5）加上一个被删掉了的区域Ⅰ，图中共有110个区域。现在已有两个加德内地图了，那一个是对的，笔者也不知道。这时图5中标有Ⅰ的区域才是只和三个区域相邻，就这样，该区域也是不能删去的。万一除了该区域外的其他所有区域只用三种颜色可以着色时，这不就把一个本来是4色的图误认为成了3色图吗。这不就是影响了着色结果吗。所以与图2的图g109所对应的加德纳地图也应是是有110个区域，而不是109个。

（4）加德纳图的对偶图的点次序列：
① 在图2 中的《图说四色问题》一书中的加德纳图的对偶图g109中，由于在顶点90和顶点108之间多画了一条边，所以在这种情况下，图中的4度顶点有2个，5度顶点有18个，6度顶点有87个，没有7度顶点，10度顶点有1个，14度顶点有1个，共计109个，该图的点次序列应是42518687101141；图2中如果不计算这条平行边时，在这种情况下，图中的顶点108的度将由5变为4，顶点90的度将由14 变为13，所以4度顶点变成了3个，5度顶点变成了17个，6度顶点仍是87个，同样也没有7度顶点，10度顶点还只有1个，增加了13度顶点1个，原来的14度顶点没有了，共计还是109个，该图的点次序列应是43517687101131。
② 可是《图说四色问题》一书中的第49页的表3.1中加德纳图的对偶图g109的点次序列却是4351868571101131，不知是为什么。也不知为什么又出现了一个7度的顶点。

③ 图g109的点次序列应是42518687101141或43517687101131，6度顶点均为87个，约占全部顶点的80%，而不是许教授在书中第53页所说的“图g109的6次节点数量很大，为85个，在全部节点（109个）中所占的比例达78%”，这一说法在第70页中也有，也是不对的。既然加德纳图的对偶图已画错了，那么书中第46页的“我们们处理的最大图是加德纳的那个难四色图，该图含110个节点（去一个3次点，余109个节点）”就成了多余的话了。
④笔者按《图说四色问题》一书中图1.11的加德纳图所做的对偶图图3和图4的点次序列分别是：图3中缺少顶点73和顶点79，共有113个顶点，其中4度顶点3个，5度顶点16个，6度顶点88个，7度顶点2个，8度顶点2个，9度顶点1个，10度顶点1个，点次序列为43516688728291101，6度顶点多达88个，这时6度顶点才占顶点总数113个的78%；图4中共有115个顶点，其中4度顶点2个，5度顶点19个，6度顶点90个，7度顶点2个，没有8度顶点，9度顶点1个，10度顶点1个，点次序列为425196907291101，6度顶点达到90个，占总顶点数115个的78%。
6、人脑与电脑那个更聪明：
许教授在书中第47页说：“Maple软件其实是一位机器数学专家、大师。它的数学知识的深度、广度已经是人类数学家不能匹敌。你学会用它，你就有了一位数学大师随时做你的助手、老师。”这三句话，前一句和后一句都是对的，但中间一句不对，说得有点过火了。什么时候人都是第一位的，计算机只是一种运算速度特快的工具而已。首先计算机是人创造的，并且是要人去操作的。人不给它输入计算程序，它什么也不会做的。说“它（指计算机——笔者注）的数学知识的深度、广度已经是人类数学家不能匹敌”，那它还能比设计Maple软件的那些科学家的知识的深度和广度还要大吗，如果不是这些人，计算机它能给图着色吗，恐怕它连什么是图也不知道。的确，“Maple软件其实是一位机器数学专家、大师”，有了它，并且要在人的操作下，它可以带替人做许多工作，且比人快得无法比拟。但光有它，没有人去操作，计算机还是什么也不会做。所以只有“学会用它”，你也才“就有了一位数学大师随时做你的助手、老师”。从这一点上看，人脑比电脑是更聪明的，人能创造电脑并且会去运用它。
7、塔特图D46T的对偶图g25T的连通度是多少：
许教授在书中对连通度是这样定义的：“一个图的连通度是4，其含义是：这个图至少要删掉4个点，才能破坏其连通性，使它变为不连通。在通信网络里，如果说该网络图的连通度是n，那么网络中至少应有n个节点遭破坏，才能使网络变为不连通（此时，网络中至少有两个点之间的通信中断）。

《图说四色问题》一书中所画的塔特图D46T如图6所示。这是一个各个顶点的度均为3的3—正则图，即书中所说的平面三次图。这个图的对偶图应是一个极大图，各个面均是3—边形。塔特图D46T中的最小圈是4—圈，其对偶图g25T中顶点的最小度应是4，应该说塔特图D46T的对偶图图g25T的连通度是4，可许教授在书中第49页倒数第4行和第51页倒数第3行中两次都说到“与塔特（反例）图对偶图的极大平面图g25Tutte的连通度仅仅为3”，这是不对的。

（未完，接下贴）

雷明85639720

废话，你没同来逛逛就行了，说那么些废话干什么呢。