泰特定理（猜想）正确否？

雷  明

（二○一七年三月十二日）

 

1  什么是泰特猜想或者泰特定理

有关文献中对泰特猜想或泰特定理的描中下：

1、1  许寿椿教授在《图说四色问题》一书中说：

“1880年泰特（Tsit）根据另外一个猜想‘每个平面三次图都有哈密顿圈’给出四色猜想的另一个证明。……”（第5页）

“泰特于1880年的证明，在60多年后，也被发现有误。……，象泰特的三次图哈密顿性、三边着色与四着色关系等等结果，都被后人接受，并计入图论发展的历史。……”（第6页）

http://s10/mw690/001MUq8Tzy79tn0C6IVa9&690

 

“泰特猜想64年后，直到1946年，著名图论大师塔特（Tutte）构造出一个没有哈密顿圈的平面三次图，即塔特反例图D46T（或D（g25T））（图1.4）。这时人们才发现，泰特的四色定理证明又错了。”与此同时，许教授在塔特图旁边又给出了一个1966年由Lederberg和Bosak分别构造的、由38个顶点构成的、所谓的“现今已知最小的非哈密顿的平面三次图” D38b（或D（g21b））。（第7页至第8页）塔特图与最小的非哈密顿平面三次图分别如图1和图2。

http://s8/mw690/001MUq8Tzy79tn1N9htc7&690

 

……………………

“泰特猜想：每一个三连通平面三次图D都有哈密顿圈。”（第113页）

“泰特还从图D有哈密顿圈，推导出与D对偶的极大平面图g必定有四着色。从而给出了四色定理的一个证明。泰特这个证明，实际上是从D有哈密顿圈，推导出图g有树—树型四着色。泰特当时并不知道树—树型仅仅是一种四着色类型，也不知道有的图g根本就没有树—树型四着色，或者是，他还根本没有注意到着色类型，仅仅注意到图g可以着四色，所以其结论有错。原本他的结论确切的应该是：‘图D有哈密顿圈是图g有树—树型四着色的充分条件’。2002年牛津大学版关于四问题的专著中给出了这个充分性证明。”（第113页）。

许教授这里所说的“三次平面图”指的就是“各顶点度度都是3的3—正则平面图”。也就是地图的原型图。地图中所有的顶点都是连着三条边界线，这就是所谓的“三界点”，即平时人们所说的“三不管地区”。

1、2  沙持朗在《图论导引》一书中说：

“Tait发现，若所有三度地图的区域都能够用4种或者更少的颜色来染色，则所有平面图的区域就能够用4种或者更少的颜色来染色。”（第253页）

“Tait证明了如下结论：‘定理10.18  三度地图G的区域能够用4种或者更少的颜色来染色当且仅当χ₁（G）＝3’。”

“实际上，3正则的3边染色也称为Tait染色。每个3正则图G都有偶数阶，并且如果G是Hailton圈C的边可以交替地染成（不仿设为）红色和兰色，移除这些边可以得到一个1因子，其中的边可以染成（不仿设为）绿色。Tait证明了，若所有的3连通且3正则的平面图都是3边可着色的，则所有三度地图也都是3边可染色的。根据定理10.18，为了证明四色定理，只要证明每个3连通的且3正则的平面图都具有边色数3就足够了。显然，若每个3连通的且3正则的平面图都是Hamilton的，则证明就完成了。由于Tait相信这些图都是Hamilton的，所以就深信自已已经证明了四色定理。虽然Tait的‘证明’的缺点最终被指出，但直到1946年，William Tutte才给出一个非Hamilton的3连通且3正则的平面图；见图10.21。”（第254页）

1、3  徐俊杰在《数学四色问题证明》一书中说：

“Tait定理：四色问题成立，当且仅当每一个三次平面图都是3—边着色的。（第11页）”他在经过了一番“证明”之后得出“推论”：“若果一个三次平面图是4—面可着色的，即也是3—边着色的”（第13页），并且也对四色猜测给出了一个所谓的“证明”。他的书最终得到了一个“每一个三次平面图都是3—边着色的，进而四色问题成立。……同理可证，每一个三次平面图都是4—面可着色的，进而四色问题成立”（第70页）的结论。

1、4  韦斯特在《图论导引》一书中说：

“由于添加边不会使得通常的着色变得更容易。为了证明四色定理，只需证明所有三角剖分均是4—可着色的，即证明所有三角剖分的对偶图都是4—面可着色的。平面三角剖分G的对偶G^*是一个3正则2—边连通平面图。对于这些图，Tait证明了：真4—面着色等价于真3—边着色。（第240页）

“7.3.2  定理（Tait［1878］）一个2—边连通3—正则平面图是3—边可着色的当且仅当它是4—面可着色的。（第240页）”在进行了所谓的“证明”之后得到：“四色定理就归约为寻找可平面图的Tait着色，对Tait着色存在性的论断就是Tait猜想，它与四色定理等价。（第242页）

“Grinberg定理：任意哈密顿3—正则图均有Tait着色。Tait相信这即完成了四色定理的证明，因为他假定3—连通3—正则平面图均是哈密顿图。尽管证明过程中的错误早就被发现了，但直到1946年才找到一个明确的反例。后来，Grinberg［1968］找到了一个必要条件，由此产生了很多3—正则3—连通非哈密顿可平面图。其中包括习题16中的Grinberg图。”（第242页）

1、5         卡波边柯在《图论的例和反例》一书中说：

“并非每个三次的3—连通的可平面图是Hamilton（哈密顿——雷注）的。考虑Tutte（塔特——雷注）图T。”（第159页）

“Tutte曾猜想每个三次的三连通的偶图是Hamilton的。下面的例子J.D.Horton的例子说明这是假的。”（第162页）

2  泰特猜想的正确叙述

从以上有关文献中对泰特猜想或泰特定理的描述看，应该说泰特猜想和泰特定理都是一回事，只是叫法不同而已。以下我统一叫做泰特猜想。只所以叫做猜想，是因为以上的文献中都只说“泰特已经证明了”该猜想，但并没有给出泰特本人的证明，而是文献的作者自已在进行证明。所以也只能说它是一个猜想。

泰特猜想应该说以下的说法都是可以的：

①　“每一个三连通平面三次图D都有哈密顿圈（许寿椿语）。”

②  “Tait证明了如下结论：‘定理10.18  三度地图G的区域能够用4种或者更少的颜色来染色当且仅当χ₁（G）＝3’（沙特朗语）。”其中χ₁（G）表示是图G的边色数。

③  “为了证明四色定理，只要证明每个3连通的且3正则的平面图都具有边色数3就足够了（沙特朗语）。”

④  “四色问题成立，当且仅当每一个三次平面图都是3—边着色的（徐俊杰语）。”

⑤  “若果一个三次平面图是4—面可着色的，即也是3—边着色的（徐俊杰语）。”

⑥  “Tait证明了：真4—面着色等价于真3—边着色（韦斯特语）。”

⑦  “一个3—边连通3—正则平面图是3—边可着色的当且仅当它是4—面可着色的（韦斯特语）。”

⑧  “四色定理就归约为寻找3—连通3—正则可平面图的Tait着色。对Tait着色存在性的论断就是Tait猜想，它与四色定理等价（韦斯特语）。”

3  分析

3、1  从有关文献中对泰特猜测的描述中可以看出，都说泰特证明了他的猜想或定理，但又没有介绍泰特是如何证明的。泰特1880年证明四色猜测时，主要是以“每个平面三次图都有哈密顿圈”的猜想为依据的。但上述文献中却都说泰特“证明过程中的错误早就被发现了”，“虽然Tait的‘证明’的缺点最终被指出”，但却都没有指出其“错误”和“缺点”是什么，而只是说“直到1946年，William Tutte才给出一个非Hamilton的3连通且3正则的平面图”和“直到1946年，著名图论大师塔特（Tutte）构造出一个没有哈密顿圈的平面三次图，即塔特反例图D46T（或D（g25T））。这时人们才发现，泰特的四色定理证明又错了。”显然，由于没有一个文件提到泰特的具体证明，也就不可能发现泰特证明中的“真正”的“错误”是什么，而只是在发现了还存不可哈密顿的（无哈密顿时圈）3—正则平面图或地图后，才认为泰特的证明是错的。当然这种否定也不能说不对，因为泰特的证明就依据的是“每个平面三次图都有哈密顿圈”，现在已经发现了不可哈密顿的平面三次图，当然否定泰特的证明也是有根有据的了，是自然而然的事。

3、2  现在的问题是，泰特猜想成立不成立并不重要，重要的是能否证明每一个平面三次图（地图）都是可3—边着色的。只要这个是真（正确的），再进一步证明泰特猜想是否正确才是有价值的。也就是说，如果泰特猜想是正确的，即泰特猜想与四色定理等价，那么，我们只要能证明任何平面三次图都是可3—边着色的，也就证明四色猜测是正确的；或者不管泰特猜想正确与否，在证明了每个三次平面图都是可3—边着色的以后，再继续证明三次平面图（地图）都是可4—面着色的也是可以的。

4         3—正则平面图一定是可3—边着色的

4、1  3—正则平面图的顶点，边，面三者间的关系

设3—正则平面图的顶点数是v，则该图的总度数是3v，因为一条边是两度，所以该图的边数e＝3v／2＝1.5v，即边数是顶点数的1.5倍。又因为图的顶点数和边数都是整数，所以该图的顶点数又必须是偶数。把v和e代入平面图的欧拉公式得该图的面数f＝v／2＋2。图1的塔特图（3—正则平面图）的顶点数v＝46，是偶数，边数e＝1.5v＝1.5×46＝69，面数f＝v／2＋2＝46／2＋2＝25；图2的最小非哈密顿平面三次图顶点数v＝38，是偶数，边数e＝1.5v＝1.5×38＝57，面数f＝v／2＋2＝38／2＋2＝21。计算结果均与图的实际参数相同。

4、2         3—正则平面图一定是可3—边着色的

由于3—正则平面图的顶点数一定是偶数，所以我们一定可以把图中的边划分为若干个偶圈（可哈密顿的图就是一个遍履，所以可哈密顿的3—正则平面图可以只划分一个偶圈）而不漏任何一个顶点。每个圈都是由相同的1—2—1的边2—色圈构成，这些边2—色圈以外的任何边，都只连接着这些边2—色圈上的、分别着有1和2两种颜色的边，而这些边之间又互不相邻，全部给其着上第三种颜色是完全可以的。这就证明了任何3—正则平面图一定都是可3—边着色的。

4、3  泰特猜想是否正确的问题

因为泰特猜想最初所依据的基础是“每个平面三次图都有哈密顿圈”这个猜想的，而并不是以任何3—正则平面图均可3—边着色为依据的，所以尽管他证明了“三度地图G的区域能够用4种或者更少的颜色来染色当且仅当χ₁（G）＝3”和平面三次图的“真4—面着色等价于真3—边着色”，以及他最终认为他证明了四色猜测，所有这些都应该说是错误的。因为他证明所依据的基础都是错的，还能得出正确的结论吗。最大只能象许寿椿教授所说的那样：“图D（即平面三次图——雷注）有哈密顿圈是图g（即D的对偶图——雷注）有树—树型四着色的充分条件”，而不是必要条件。因为还有大量的非哈密顿的平面三次图也是可4—面着色的。虽然“泰特还从图D有哈密顿圈，推导出与D对偶的极大平面图g必定有四着色。从而给出了四色定理的一个证明”。但这个证明也是不完整的，只是对于部分可哈密顿的平面三次图是适用的，而没有解决另一部分不可哈密顿的平面三次图是否可以可4—着色的问题。

4、5      实例：塔特图与最小三次平面图的3—边着色

塔特图3—边着色如图3。最小非哈密顿平面三次图的3—边着色如图4。

http://s15/mw690/001MUq8Tzy79tn3n90i8e&690

 

由于有塔特图等图的陆续构造出来，使得泰特用以证明四色猜测的主要依据“每个平面三次图都有哈密顿圈”发生了动摇，并不是所有的平面三次图都是可哈密顿的。从这里的证明中可以看出，只要是平面三次图，是不是可哈密顿的并不关紧要，紧要的是任何平面三次图都一定是可3—边着色的才是关键。这才是泰特猜想——“对Tait着色存在性的论断就是Tait猜想，它与四色定理等价”——的关键。

http://s11/mw690/001MUq8Tzy79tn4CLlUfa&690

 

现在，可以说我们已把这个关键盘性的问题解决了，任何三次平面图都是可3—边着色的。如果说泰特猜想是正确的，那么到此可以说四色猜测就得到了证明是正确的。至于泰特猜想真的是否正确，我们也可以不去管它。可以想办法证明可3—边着色的3—正则平面图（地图）是否可以4—面着色，也就可以使四色猜测得到证明。

5  可3—边着色的3—正则平面图（地图）是可以4—面着色的

可3—边着色的3—正则平面图（地图）中一定存在1—2—1，1—3—1和2—3—2三种边2—色圈，每一种边2—色圈都把画图的面分隔成了若干部分。把一种边2—色圈所分隔成的区域（每个这样的区域包括了图中的若干个面）分别相间的着以A，B二色，而把另一种边2—色圈所分隔成的区域（每个这样的区域也包括了图中的若干个面）也分别相间的着以C，D二色。这样，在图中颜色叠加的结果，便新产生了四种不同的颜色AC，AD，BC和BD，使得图中的每一个面都有一种颜色，且相邻的两个面具有不同的颜色。这就是韦斯特和徐俊杰在证明时所用的方法。但徐俊杰说得比较明白，而韦斯特说得让人看不懂。

我们对前面的最小的平面三次图（图2）用这种颜色叠加法对其面着色如下：图5是在1—2—1边2—色圈内外分别着A，B的结果，图6是在1—3—1边2—色圈内外分别着C，D的结果。图7是图5和图6颜色叠加后的结果，若用红色替代AC，用黄色替代AD，用兰色替代BC，用绿色替代BD，可得到彩色地图如图8。

http://s9/mw690/001MUq8Tzy79tn5O4pGe8&690
      http://s2/mw690/001MUq8Tzy79tn6Wb6111&690

 

 

该最小平面三次图的对偶图的4—着色如图9。

塔特图同样也可以用颜色叠加法进行4—面着色，其对偶图也是可4—（顶点）着色的，这里就不再画图了。

到此，就证明了任何平面三次图（3—正则的平面图，也即地图）都是可4—着色的，也就证明了地图的四色猜测是正确的。

http://s7/mw690/001MUq8Tzy79tn8mAbcf6&690
      http://s10/mw690/001MUq8Tzy79tn9lh3Pf9&690

       http://s6/mw690/001MUq8Tzy79tnanNljb5&690

 

 

 

6  四色猜测的证明

由于3—正则平面图的对偶图是一个极大平面图（即每个面都是三角形的图），给地图的面着色就相当于给其对偶图——极大图——的顶点着色；所以极大平面图的色数也是不大于4的；由极大图通过去点或拆边后得到的非极大平面图的色数只会比原来极大图的色数减小而不会增大，所以也就有任何平面图的色数不大于4的结论，即平面图的四色猜测也是正确的。这就完整的证明了四色猜测是正确的。

7         一个有待研究的技术性问题

我曾提出过用这种颜色叠加的的方法证明四色猜测是否合适的问题，因为A，B，C，D四种颜色叠加的结果只能得到AC，AD，BC和BD四种颜色，既不可能大于4，也不可能小于4，是不可能得出任何地图（平面三次图）的色数一定是小于等于4的结论的。这种方法用在证明时还是可以，反正不大于4。但在着色时，是否可以把一个原本面色数是3的3—正则图，给着上了4种颜色呢。是的，是存在这种情况的。比如正六面体的着色（如图10和图11）。

http://s12/mw690/001MUq8Tzy79tncW4Zlbb&690

 

用颜色叠加法对正六面体着色时，既可以得到4—面着色图（如图10），也可以得到3—面着色的图（如图11）。这是什么原因造成成的，一下子还弄不明白。只能看出两个图不同的地方是：在着3—色的图11中正六面体的各个四边形面，边所占用的颜色数都是最小的2；而着4—色的图10中正六面体的各个四边形面，边所占用的颜色数不都是最小的2，有的是占用了3种颜色的。是不是在进行3—边着色时，要考虑尽量使各面的边所占用的颜色数达到最小是一个条件，如何解决这一问题，还有待于进一步研究。

http://s15/mw690/001MUq8Tzy79tnga50aae&690
      http://s12/mw690/001MUq8Tzy79tnhmo5R0b&690

 

 

我们再来看看图12这个最简单的地图的例子。这是海地岛的地图，其上有两个图家——海地和多米尼加，四周是海洋。该地图（三次平面图）中有两个顶点，三条边，三个面。其3—边着色如图12，a。这个地图用颜色叠加法却得到了一个3—色图，与实际情况是相符的。这个地图的确三种颜色就够用了。当然了，因为这个地图总共只有三个面，当然是不可能用到四种颜色的。这当然也不能说明这种颜色叠加法就一定是正确的。

8  以下这样的解释是否适合

上一节谈到了正六面体（4—楞柱）的问题，这个图本来就是一个可哈密顿的三次平面图，一定是有一个可经过所有顶点的大偶圈的。图10就是这样，3条边2—色圈中，就有两条是哈密顿圈，是遍履。这就是我们前面在证明3—正则平面图都是可3—边着色一节中说的：可哈密顿的图就是一个遍履，所以可哈密顿的3—正则平面图可以只划分一个偶圈。但这并不是说这样的图只能划分成一个偶圈，图11就反映了这一事实，三条边2—色圈都不是哈密顿的，也都不是遍履。而表现出来的则是如上节所说的：在着3—色的图11中正六面体的各个四边形面，边所占用的颜色数都是最小的2；而着4—色的图10中正六面体的各个四边形面，边所占用的颜色数不都是最小的2，有的是占用了3种颜色的。

http://s6/mw690/001MUq8Tzy79tniEDDDf5&690

 

    图13中的海地岛地图，3—楞柱，5—楞柱等寄数柱面的楞柱，本来就应是4—面着色的。从图中可以看出，它们也都是可哈密顿的，且在3—边着色时，只能划分出一个大偶圈，即哈密顿圈。颜色叠加的结果一定是产生了四种新的颜色，正好这几个图也都是4—面着色的。但对于如图14所示的4—楞柱，6—楞柱等偶数柱面的楞柱来说，情况就不象图13中那几个图那么简单。

    http://s5/mw690/001MUq8Tzy79tnllwhe34&690

      http://s12/mw690/001MUq8Tzy79tnojBXlbb&690

 

 

柱面数为偶数的楞柱也都是可哈密顿的平面三次图，但我们在对其进行3—边着色时，既可以划分成有两条边2—色圈都是哈密顿圈的3—边着色模式（如前面正六面体的图10和这里6—楞柱的图15），也可以划分成没有任何边2—色圈是哈密顿圈的3—边着色模式（如前面正六面体的图11和这里6—楞柱的图16）。两种边着色模式分别对应着不同的面着色模式，前者是4—面着色的，后者3—面着色的。因此说，在对三次平面图进行三边着色时，一定要使所有边2—色圈都不是哈密顿圈，就可以得到正确的着色结果。具体表现就是边二色圈一定要把画图的面分隔成三个以上的部分。具本情况，请读者看图就明白了。

http://s11/mw690/001MUq8Tzy79tnpE3zQea&690

 

    从正六面体和6—楞柱的例子可以看出，只有可哈密顿的三次平面图在3—边着色时，才可能有哈密顿的边2—色圈出现，而非哈密顿的三次平面图在进行3—边着色时，是不可能届现可哈密顿的边2—圈的。所以说泰特只是看到了一部分可哈密顿的三次平面图是既可以3—边着色，也可以4—面着色的，就认为三次平面图的可3—边着色是与其可4—面着色等价的；而没有看到还有另一部分非哈密顿的三次平面图同样是既可以3—边着色，也可以4—面着色的。所以说泰特的猜想是不真的，也就是不证确的。

本人水不有限，只能看到这一点点问题。请爱好四色问题的网友们对这一问题进行研究。

9  韦斯特与徐俊杰用的颜色叠加法是否行得通的问题

①　颜色叠加法的原理是什么，不太明白，有待于研究。

②　颜色叠加法只能说明叠加的结果新产生四种颜色，不能说明为什么不会产生大于四种和少于四种的颜色数量。

③　颜色叠加法不能解释为什么有些图本来面色数是3，而叠加的结果却是4这一现象。

④　徐俊杰对可4—面着色的三次平面图的可3—边着色的证明则是有说服力的，是正确的。若用A，B，C，D代表四种颜色，然后他设三次平面图的两个面的边界线的颜色为：A＋D＝1，B＋D＝2，C＋D＝3，A＋B＝3，A＋C＝2，B＋C＝1。可以看出徐先生认为着A，B二色的两个面的边界线，与着C，D二色的两个面的边界线是不可能相邻的，即不可能相接的，都用3表示是完全可以的；同样的原因，把着A，C二色的两个面的边界线，与着B，D二色的两个面的边界线都用2来表示；把着A，D二色的两个面的边界线，与着B，C二色的两个面的边界线都用1来表示。把并把数字1，2，3，按照图中各颜色的面的相邻关系，分配给图中的各条边。图中绝不会出现同一个顶点连有相同的数字的现象，就证明了可4—面着色的3—正则平面图一定是可以3—边着色的。他的结论原话是：“如果一个三次平面图是4—面可着色的，即也是3—边着色的”。可4—面着色的6—楞柱和5—楞柱用此方法得到的3—边着色如图17。

http://s10/mw690/001MUq8Tzy79tnr8I0F29&690

 

⑤　如果说韦斯特和徐俊杰对泰特猜想的证明是对的，正确的，则就说明泰特猜想也是正确的，即三次平面图的可3—边着色与可4—面着色等价，我们在本文中又进一步证明了任何平面三次图都是可3—边着色的，那么就完全可以说四猜测就已经得到了证明是正确的。

⑥　请网友们多提意见。

 

 

雷  明

二○一七年三月十二日于长安

 

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

http://www.chinaphd.com/cgi-bin/topic.cgi?forum=5&topic=3263&show=0