72、对李建中所译《图论导引》一书第214页的评论

雷明85639720

这是我《四色问题与欧拉公式》一书中第六章《四色猜测与欧拉公式》一章中的第66节《对李建中所译《图论导引》一书第214页的评论》一节


72、对李建中所译《图论导引》一书第214页的评论
1、该书中第214页的原文
为了使读者能更好的发现、理解其中的错误，这里需要把李建中、骆吉洲翻译的［美］Douglas  B•West 所著的《图论导引》（原书第2版）（书名原文：Introduction  to  Graph  Theory，机械工业出版社，北京京北制版厂印刷，2006年2月第1版第1次印刷）一书中的第214页中的一段对赫渥特的地图着色公式 （G）≤ 的论述所得的结论：“当γ＝0时，这里给出的这个关键不等式不成立，因此对可平面图来讲这里的论述是无效的，尽管γ＝0时公式简化为 （G）≤4。……”及其所谓的“证明”全部抄录如下：
“6.3.25定理（Heawood公式——Heawood［1890］）  如果G可以嵌入到Sγ（γ＞0）上，则 （G）≤ 。
“证明  令c＝（7＋ ）/ 2。只要证明能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1，就可以通过n（G）用归纳法得出 （G）的这个界。由于 （G）≤c对顶点数最多为c的任意图均成立，故只需考虑n（G）＞c的情况。
“我们用引理6.3.24证明平均度（当然也是最小度）最多为c－1。下面的第二个不等关系可以马上从γ＞0和n＞c得到。由于c满足c2－7c＋（12－12γ）＝0，因此有c－1＝6―（12―12γ）/ c，故平均度满足上界要求。
“ ≤ ≤6－ ＝c－1。
“当γ＝0时，这里给出的这个关键不等式不成立，因此对可平面图来讲这里的论述是无效的，尽管γ＝0时公式简化为 （G）≤4。……”
以上引文中所说的“引理6.3.24”，就是指由多阶曲面上的欧拉公式n－e＋f＝2－2γ推导出来的任意图的边与其亏格的关系e≤3（n－2＋2γ）（其推导过程见前第64节《完全图的亏格》一节中的“2、不同亏格的图中边与顶点的关系”一段中公式（6—8）的推导过程），这个公式在该《图论导引》一书书中也有。由于有e≤3（n－2＋2γ），所以也就有 ≤ 。公式e≤3（n－2＋2γ）就是我们在前面第64节《完全图的亏格》一节中所得到的公式（6—8）e≤3v＋6（n－1）＝3（v－2＋2n）。不过这里不同的是：我们这里的v、e、γ、n分别是图顶点数、边数、色数和图（或曲面）的亏格；而以上所引原文中的n、e、 （G）、γ分别是图的顶点数、边数、色数和图（或曲面）的亏格，Sγ是亏格为γ的曲面；c是作者令其为c＝（7＋ ）/ 2的一个常数，这个常数对于某个亏格值的曲面只有一个，实际上就是能嵌入到该曲面上的图的最大色数，如γ＝0时，c＝4＝ （G），γ＝1时，c＝7＝ （G），γ＝2时，c 8.42，其取整后就是c＝8＝ （G）等等。
2、对该书第214页的评论
    首先看一下书作者的“令c＝（7＋ ）/ 2”是一个什么名堂。大家都很熟悉（7＋ ）/ 2就是赫渥特的地图着色公式向下取值前的形式，其向下取值后就是能嵌入亏格为γ的曲面上的图的最大色数。那么这里的c就应该是色数，也可以认为c是完全图KC的顶点数，因为完全图的色数与其顶点数是相等的。
笔者认为该《图论导引》一书中以上的这段话中有比较多的错误，现在一个个的进行分析：
1、书中说的“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”这一结论是不够严密的。
从前面第66节《任意图中各个参数间的相互关系》一节中知道，能够嵌入到Sγ上的图的亏格最大只能是γ，在保证图的亏格不发生变化的情况下，若在任意图的面中增加一个顶点最多只可能增加三条边，这是因为图中可能有三边形面，只能增加三条边，否则图的亏格就有可能增大。当图的亏格大于1（密度一定大于7）时，图的平均度随顶点的增加是一个减函数，其值是6＜δ≤c－1的，因为增加一个顶点所增加的三条边所产生的度数6小于完全图Kc（c＞7）的平均度c－1≥6，该函数的下极限是6；而当图的亏格小于等于1且密度小于等于6时，图的平均度随顶点的增加是一个增函数，其值是c－1≤δ＜6的，也因为增加一个顶点所增加的三条边所产生的度数6大于完全图Kc（c＜7）的平均度c－1≤6，该函数则是上极限是6；而只有亏格是1密度是7的图的平均度是一个常数6，不随顶点的增加而变化，这是因为增加一个顶点所增加三条边所产生的度数6下好就是完全图K7的平均度6，这个6就是以上两函数的极限。由于K7、K6和K5本身的亏格就是1，其平均度也不可能大于6，所以也可以认为亏格为1但密度是7、6 和5的图中“有一个顶点的度至多为c－1”也是可以的。由于有这样的不同，所以就产生了亏格大于等于1的图中至少存在一个顶点的度是小于等于c－1的；而亏格小于1的图中可能会存在平均度是大于等于c－1的图。例如亏格为0的正八面体和正二十面体的顶点数分别是6和12，平均度分别是4和5，都大于用亏格为0按公式c＝（7＋ ）/ 2计算出的c－1＝4－1＝3，它们的顶点数都大于c，即有n＞c关系。所以说“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”这一结论是不够严密的。
另外从书作者为了证明“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”的结论，前提规定的条件“γ＞0和n＞c”来看，这个条件显然说的是亏格为γ≥1和n≥8（因为当γ＝1时，c＝（7＋ ）/ 2＝7）的非平面图的条件，而书作者却硬说是“任意简单图”。可能有人会说，这里本来就不包括γ＝0且n≤c的情况。那么我要问，你本来就是要进行证明赫渥特的地图着色公式 （G）≤ 对于在γ＝0条件下是不成立的，而你却提前就把γ＝0排除在外，这可能是不合适的吧，这能叫证明吗。即就时按书作者的说法在γ＝0时，赫渥特的地图着色公式是不成立的，那么你把K5、K5和K7又放在那里了呢，它们可都是符合“γ＞0”的呀，其各顶点的度均是小于或等于“c－1”＝7－1＝6的，但其顶点数n却均小于等于c＝7的，即有n≤c的关系，这又不符合你的“n＞c”的条件。K5、K6和K7这三个图可都是人所共知的非平面图，其色数分别是 （K5）＝５， （K6）＝6和 （K7）＝7，它们的色数可都是 （G）≤7，都是小于等于7的呀。难道γ＝1时赫渥特的地图着色公式也不成立吗。另外，顶点数大于等于7的所有完全图的顶点数也都是不符合“n＞c”的条件的，其顶点数n都是等于与其相应的亏格条件下的“c”值的，即有n＝c。
这里的“简单图”是什么概念，非常的不明确。从字面上理解，应与图论中的单纯图（不含有环和平行边的图）差不多，这也可能是各人的译法和叫法不同的原因吧。但在这里，书作者把亏格为γ＝0的平面图都已全部排除在外，却又用了一句“任意简单图”，难道不含环和平行边的平面图不是“简单图”或单纯图吗。既然说的是“任意简单图”，为什么又要把γ＝0的真正是“简单图”的平面图排除在外呢，γ＞0的非平面图能叫做“简单图”吗。不仅如此，但按书作者所规定的条件“γ＞0和n＞c”，实际上也把亏格大于等于1的非平面的完全图全部也都排除在外了。
根据前面第67节《任意图的不可避免（度）集》中的公式6—42和6—43可以看出，具有“一个顶点的度至多为c－1”的图只适合于亏格大于等于1的图。具有“一个顶点的度至多为c－1”这句话实际上就是亏格大于等于1这一类图的不可避免度集。除此之外的亏格为0的任何图的不可避免度集则是“具有一个顶点的度至多为5”，即δ≤5。该《图论导引》的作者只看到了亏格大于等于1这一类图的不可避免度，而没有看到除此之外的另一类图的不可避免度。
2、书中说证明赫渥特的地图着色公式“只要证明了能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1就可以……”，这一说法也是错误的。以上（1）中已说明了“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”的结论是错误的，那么这里所说的“只要证明了能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1就可以……”怎么怎么的说法当然也就是错误的了。既然书作者认为“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”的这一结论是正确，那么在书中就应给以证明，可书中为什么没有给以证明呢。在这一句话“只要证明了能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”后面，书作者紧接着说“就可以通过n（G）用归纳法得出 （G）的这个界。”但是这里并没有看到书作者用了什么样的归纳法，也没有看到他得出的 （G）的界是什么。除此之外，书中也并没有证明在当亏格大于等于1时，赫渥特的着色公式为什么又是成立的。
3、书中有“平均度（当然也是最小度）最多为c－1”这句话也是错误的。平均度与最小度是两个不同的概念，不能这样的用括号进行注解。只能说有可能某些图的平均度与最小度在数值上是相同的，如四面体，正六面体，正八面体，正十二面体，正二十面体以及所有的完全图都是这样，但这里并不都是等于c－1＝4－1＝3；而只有正四面体（或完全图K4），正六面体，正十二面体的平均度与最小度既是相等的，且是等于c－1＝３；而正八面体，正二十面体的平均度与最小度虽相等，但却不等于“c－1”＝ 4－1＝3，而分别是等于4（正八面体）和5（正二十面体），都是大于“c－1”的；而在平均度与最小度二者不相等的情况下，这时的最小度则一定是小于平均度的，但也不一定是小于“c－1”的；只有图是完全图时才可能有平均度等于最小度，也等于“c－1”的情况。所以“平均度（当然也是最小度）最多为c－1”这样的说法也是错误的。“平均度（当然也是最小度）最多为c－1”这一结论至少对于亏格为0的平面图是不成立的，所以也不能用“任意简单图”来概括它，这在（1）中已经进行了评论。
从我们前面第66节《任意图中各个参数间的相互关系》一节中的公式（6—33）、（6—34）和图6—21知道，亏格大于等于1 的图的平均度最大只能是该亏格条件下的“c－1”的值，所以说该《图论导引》一书中说的“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”这句话应说成是“能够嵌入到Sγ（γ≥1）上的图中一定有一个顶点的度至多为c－1”，当然其平均度或最小度也是小于等于“c－1”的。这显然是亏格大于等于1的图的性质，书作者却硬要拿来对所有亏格的图而言，当然就是不对的了。而对于密度小于等于6的图（包括所有亏格为0的平面图和亏格为1但密度为4、5 和6 的非平面图）则有“图中至少有一个顶点的度是小于等于5 的”，其中对于亏格为0的平面图来说，这个5就是大于c－1＝4－1＝3的，这一点作者是没有注意到的。
4、书中还有“令c＝（7＋ ）/ 2。……。由于 （G）≤c对顶点数最多为c的任意图均成立，故只需考虑n（G）＞c的情况。”
这一点我们不难验证顶点数小于等于c的图的色数一定是小于等于c的，也就是一定小于等于（7＋ ）/ 2的。例如亏格是1的典型的非平面图K3,3图的色数是2，就是小于亏格为γ＝1时的c＝ ＝7的。K5图的色数是5，也是小于其亏格1所对应的c＝7的。注意这里的c＝ 只有在γ＝0、1等个别情况下才是整数（见前面第62节《多阶曲面上图的亏格》一节中的论述），绝大多数情况下都是非整数，向下取整后实际上就是顶点数为c的完全图KC（也是该亏格γ下的顶点数最多的最大完全图）的色数 （G），而c－1就是该完全图的平均度。然而书作者是如何证明n（G）＞c时，其色数也是 （G）≤c的呢。作者说：
“我们用引理6.3.24证明平均度（当然也是最小度）最多为c－1。下面的第二个不等关系可以马上从γ＞0和n＞c得到。由于c满足c2－7c＋（12－12γ）＝0，因此有c－1＝6―（12―12γ）/ c，故平均度满足上界要求。 ≤ ≤6－ ＝c－1。”
这里所说的“引理6.3.24”，就是指由多阶曲面上的欧拉公式n－e＋f＝2－2γ推导出来的任意图的边与其亏格的关系e≤3（n－2＋2γ）（见前面第64节《完全图的亏格》一节中的推导过程），所以也就有其顶点的平均度是 ≤ 。而“由于c满足c2－7c＋（12－12γ）＝0，因此有c－1＝6―（12―12γ）/ c”则是这样得来的：
书作者已“令c＝（7＋ ）/ 2”，所以有
2c－7＝
4c2－28c＋49＝1＋48γ
c2－7c＋12－12γ＝0
即
        c2－7c＋（12－12γ）＝0
这就是所谓的“c满足c2－7c＋（12－12γ）＝0”。再继续变形得
c－7＋ ＝0
c－1－6＋ ＝0
c－1＝6－
即有
        c－1＝6―（12―12γ）/ c
把完全图的亏格公式γ＝ 进行变形也可以得到c－1＝6―（12―12γ）/ c，也可以直接从多阶曲面上的欧拉公式推导出来c－1＝6―（12―12γ）/ c。
这里的“c－1”实质上就是亏格为γ、顶点数为c的完全图Kc各顶点的平均度，其色数是c。如果我们再对c2－7c＋（12－12γ）＝0进行求解，可得到能够满足其要求的一个根是c＝（7＋ ）/ 2（该方程的求解过程可以参见本书前面的几次有关求解一元二次方程x2－7x＋12＝0的过程），这就是赫渥特的地图着色公式中亏格为γ的完全图Kc的色数，式中c既可以是色数，也可以是完全图的顶点数，因为完全图的色数与其顶点数相等。
由于同亏格的图中，最大完全图的平均度是该亏格下所有图中的最大者，所以又有
         ≤ ≤6－ ＝c－1
把上式变形
     ≤
    6cn－12c＋12cγ≤6cn－12n＋12nγ
    12c（γ－1）≤12n（γ－1）
    12c≤12n
    c≤n
从而才可以得到n≥c。其中等式对应的是完全图，不等式对应的则是非完全图。因为在亏格γ≥1的图中，非完全图的顶点数一定是大于完全图的。这个结果仍然是说明了“能够嵌入到Sγ（γ≥1）上的图中一定有一个顶点的度至多为c－1”，即亏格大于等于1的图的平均度最大只能是c－1，图中至少有“一个顶点的度至多为c－1”的特点，而并不是包括所有的图。而亏格小于1的这一类图（平面图）的平均度的上界则不是c－1，而是c＋1＝5。所以也就有正八面体和正二十面体的平均度分别是4和5，而不是c－1＝4－1＝3，其顶点数也有n≥c＝4，但其色数则是4，仍是不大于4 的。
    注意，上述的证明是作者在“用引理6.3.24证明平均度（当然也是最小度）最多为c－1”的前提下得到的n≥c，这已经就提前排除了有平均度大于“c－1”的情况的存在，而不是“从γ＞0和n＞c得到”的“平均度（当然也是最小度）最多为c－1”。但作者还要美其名曰“下面的第二个不等关系可以马上从γ＞0和n＞c得到。”实际上得到这个“不等关系”关没有用到“γ＞0和n＞c”的条件。
书作者在这里的目的是为了证明在“考虑n（G）＞c的情况”下， （G）≤c如何才是成立的，但却没有看到他的证明，而只看到他说“从γ＞0和n＞c得到”了“ ≤ ≤6－ ＝c－1”（即n≥c）。这只能说明在γ＞0的况下，图的平均度是小于等于c－1的，而不是在证明赫渥特的地图着色公式成立不成立的问题。这里的所谓“证明”除了说明了亏格大于等于1的图中一定有“一个顶点的度至多是c－1”外，并没有看到作者是如何证明在γ＞0和n＞c的条件下，赫渥特的地图着色公式是如何成立的，也更没有看到在γ＝0的条件下，赫渥特的地图着色公式又是怎么不成立的。在这样的情况下作者凭空下了结论说：“当γ＝0时，这里给出的这个关键不等式不成立，因此对可平面图来讲这里的论述是无效的，尽管γ＝0时公式简化为 （G）≤4。……”。书作者清清楚楚的说：“这里给出的这个关键不等式”是“可以马上从γ＞0和n＞c得到”的，不言而喻，也就是说对于γ＝0的图这个关键是不成立的。可这个只对于γ＞0，且只关系到图的平均度的不等式在γ＝0时成立与否与证明γ＝0时赫渥特的地图着色公式成立不成立又有什么关系呢。所以说这根本就不是什么证明。
看来书作者是头脑里固有就认为当亏格为0时，赫渥特的地图着色公式对于平面图是不适用的这样一个认识。所以也就有上面的结论。这里值得注意的是：
（1） 还有 （平均度）≤ 是从任意图的边与其亏格的关系e≤3（n－2＋2γ）得来的（在这里n是任意图的顶点数，γ则是亏格数）。由于完全图是同顶点数的图中边数最多的，所以也就有 （平均度）≤ ≤6－（12－12γ）/ n，在完全图情况下则是 （平均度）＝ ＝6－（12－12γ）/ n，也就有n＝c。
（2） 这里的 （平均度）≤6－（12－12γ）/ n与c－1≤6―（12―12γ）/ c实质上是相同的（两式中的n和c既都是完全图的顶点数，也都是完全图的色数）。应有 ＝c－1和6－（12－12γ）/ n＝6―（12―12γ）/ c，从而得到n＝c。只所以两式可以分别从不同的角度得出，但却有相同的结论，是因为推出两式的依据γ≥ 和c＝（7＋ ）/ 2以及e≤3（n－2＋2γ）都是从多阶曲面上的欧拉公式n－e＋f＝2－2γ而得到的。关于赫渥特的地图着色公式 （G）≤ 、完全图的亏格公式γ≥ 以及e≤3（n－2＋2γ）都是如何从多阶曲面上的欧拉公式推出的，请见前面第65节《赫渥特地图着色公式与四色猜测的证明》一节中的“3、本书作者从欧拉公式直接推导赫渥特的地图着色公式》、第64节《完全图的亏格》一节中的“7、完全图的亏格”和“2、不同亏格的图中边与顶点的关系”三部分。
5、书作者在“证明”之前说“由于 （G）≤c对顶点数最多为c的任意图均成立，故只需考虑n（G）＞c的情况。”请问，现在从你的推导中已经得到了n＞c的结果，为什么又说赫渥特的公式对于正八面体和正二十面体所对应的图（均为平面图，亏格为0，顶点数分别是6和12，大于由c＝ 计算出的值4，即12＞4）“不成立”呢，为什么“对平面图来说这里的论述”又“是无效的”呢。书作者“只需考虑n（G）＞c的情况”下，对于γ＞0时，赫渥特的地图着色公式成立的“证明”又在什么地方呢。实际上书作者并没有证明在γ＞0且n＞c时赫渥特的公式是如何成立的，而且就连n≤c时的情况，也没有证明赫渥特的公式对于γ＞0时是如何成立的。
6、书中认为“当γ＝0时，这里给出的这个关键不等式不成立，因此对可平面图来讲这里的论述是无效的，尽管γ＝0时公式简化为 （G）≤4。”这就是书作者认为γ＝0时赫渥特的地图着色公式“不成立”、对“平面图”来说是“无效的”的原因。他得出这样的结论的理由也是不充分的。在这里他是把只适合于亏格大于等于1的图的性质（“有一个顶点的度至多为c－1”），用来衡量任意亏格的图当然就不合适了。他认为能嵌入亏格为０的曲面上的正八面体和正二十面体所对应的图（平面图）中各顶点的平均度分别是4和5，是大于该曲面亏格为0时的“c－1”＝4－1＝3的，所以就认为γ＝0时赫渥特的地图着公色式“不成立”，而且认为对“平面图”来说是“无效的”。难道亏格大于等于1的图中至少“有一个顶点的度至多为c－1”，而亏格为0的平面图中也一定要有这样的规律吗。书作者难道就没有看到亏格为0的平面图的不可避免度集的上界正好就是5吗。正八面体和正二十面体所对应的图的色数确实又是把γ＝0代入赫渥特着色公式 （G）≤ 中所得到的结果—— （G）≤4。所以我认为书作者在这里并不是在证明当γ＝0时，赫渥特的公式是否成立，而只是从一个只适合于γ＞0的图的平均度的结论：图中“有一个顶点的度至多为c－1”出发进行判断的。而平面图中确实有象正八面体和正二十面体这样的图存在，不符合他上面的那个结论的要求。所以就直接得出了当γ＝０时，赫渥特的公式不适用的结论。这能叫做证明吗。在前面第67节《任意图的不可避免（度）集》一节中，我们已经得到了任意图的不可避免度的上界是
      
      
并且绘制了图的亏格与图的不可避免集的关系曲线图（图6—24），从图中明显可以看出，只有亏格大于等于1的图的不可避免度是小于等于该亏格下的“c－1”的，而亏格等于0的图的不可避免度则不是小于等于其“c－1”＝4－1＝3，其上界是比3大的5。某个图中所有顶点的度均大于“c－1”也是很正常的事（如正八面体和正二十面体），或者说图中不存在度小于等于“c－1”的顶点也是正常的事。也只有完全图才有平均度与最小度相等且都是“c－1”的情况。所以说“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”的结论是错误的。我们在前面第65节《赫渥特地图着色公式与四色猜测的证明》一节中，能够从多阶曲面上的欧拉公式直接推导出赫渥特的地图着色公式，本身就说明了赫渥特的地图着色公式是能够适用于亏格为0的平面图的，因为多阶曲面上的欧拉公式本来也就适用于亏格为0的平面图。赫渥特的地图着色公式在亏格为0 时的值小于等于4，这就是对四色猜测最好的证明，说明了猜测是正确的。
7、从我们所抄录的第一句话“6.3.25定理（Heawood公式——Heawood［1890］）  如果G可以嵌入到Sγ（γ＞0）上，则 （G）≤ ”看，书作者早就把亏格为0的平面图排除在赫渥特的地图着色公式之外了。从这里看，他在这里根本就不是在证明该公式对于平面图是适用还是不适用的问题，而是在证明对于亏格大于等于1 的非平面图，当图的顶点数“n＞c”大于时，赫渥特的地图着色公式是否适用的问题。可惜他用了一个“能够嵌入到Sγ上的任意简单图有一个顶点的度至多为c－1”的错误结论，且也没有说明如何在顶点数“n＞c”时赫渥特的公式又是如何适用的。