出现5色定理的根源

LIUFU

[这个贴子最后由LIUFU在 2013/02/01 08:03pm 第 3 次编辑]

一、 出现5色定理的根源
    回忆我们过去经常遇到的一幕（在离散数学教程）：它发生在归纳假设之中，（一般形式）若图G在当顶点数为N时，是5-可着色的，去证明当G的顶点数为N+1时，也是5-可着色的。  
   其中当deg(v)=5时，用到v的5邻点着5色数时采取的办法。那办法正是过去肯普用肯普链法减少了1色，把这个颜色给了待着顶点v!回忆到这里，马上打住。
   肯普当年的这一证明法，得到广泛承认，直至今天。而当年的希伍德运用此法证明了5色定理！为什么得到的是五色......？现在找到原因了，他的方法本身（Q构形-4邻点4着色）存在问题。
   在没有指出问题之前，让我们考察一个5阶轮图是否在归纳假设范围内？因此时，5阶（3色）轮图（中心有1顶点）的顶点数不多于与v相邻图的顶点数，显然是在归纳假设之内的（轮图是在可着色之内不断出现的）！故允许、有必要考虑这个轮图的色数定理的作用。该轮图是3色图，v的4邻点只占有2色，还应该有2个空余颜色；用“可着色定义”理解轮图定理就是：对颜色数的再分配结果，5阶轮图着3色；而肯泊的方法却只给空出1色来！这说明肯泊的方法严重脱离实际！这就是造成出现5色定理的根源----同时也是造成不能证明4色定理的根源。
   不过，读者要注意：在5色定理的证明中是把刚才的Q构形改变为v的5邻点着5色的构形。道理是一样的。这就是被图论工作者称之为的“肯普绝招儿”。
                二、对轮图引用的思考
    现在找到了根源，就可以克服其不足。轮图本身并不难，难的是如何把它用到归纳法的归纳假设中去！本文对它为什么是归纳假设范围之内的分析是轮图应用的关键。
   因这里的轮图与v外有公共顶点，设公共顶点数为i。在归纳假设所允许的顶点数（i+n)范围内【（i+n)=、>i+1，n>、=1】，这是一个无限的过程，轮图由始至终都伴随其中。这就保证了引用轮图是合情合理合法的！
   轮图进入图的着色，就起到了着色预警的作用！轮图定理介入证明，使“最小可着色”融入其中，给证明增加了新鲜血液。
   

雷明85639720

我来说几句   
    1、“肯普当年的这一证明法，得到广泛承认，直至今天。而当年的希伍德运用此法证明了5色定理！为什么得到的是五色......？现在找到原因了，他的方法本身（Q构形-4邻点4着色）存在问题。”中的“他的方法本身（Q构形-4邻点4着色）存在问题。”一句中的“他”作者说是指坎泊，“Q构形”作者说是指4—轮。请问，现在要给4—轮的中心顶点空出颜色，而该顶点以外的其他所有的围栏顶占已用完了四种颜色，为什么这个4—轮的4个轮沿顶点就不能也占用完4种颜色呢，4—轮的4个轮沿顶点占用两种、三种、四种颜色的情况都是可以存在的。
    2、“在没有指出问题之前，让我们考察一个3阶轮图是否在归纳假设范围内？因此时，3阶轮图（有4个点）的顶点数不小于与v相邻图的顶点数，显然是在归纳假设之内的！故允许、有必要考虑这个轮图的色数定理的作用。该轮图是3色图，v的4邻点只占有2色，还应该有2个空余颜色；而肯泊的方法却只给空出1色来！这说明肯泊的方法严重脱离实际！这就是造成出现5色定理的根源。”中的“3阶轮图（有4个点）的顶点数不小于与v相邻图的顶点数”，这里“与v相邻图的顶点数”是多少没有明确，无法比较；况且3—阶轮图不是4个顶点而是3个顶点。3—轮才有4个顶点，一个中心顶点，3 个轮沿顶点；3—阶轮图实际上是一个2—轮，即是一个2—重的K3图。

刘福

[这个贴子最后由刘福在 2013/02/02 07:10pm 第 1 次编辑]

htthttp://s12.sinaimg.cn/large/4dd633664549c4a12f32bp://s12.sinaimg.cn/large/4dd633664549c4a12f32b
这是平常心的图2，介绍Q构形及其可约性证明；请阅。

LIUFU

[这个贴子最后由LIUFU在 2013/02/01 08:14pm 第 1 次编辑]

您在（1）中说的是事实：4-轮的4个轮沿顶点用2种、3种、4种颜色的情况都是“可以”（不是最好）存在的。而我单指（专指Q构形）-----“Q构形-4邻点4着色”！用肯泊方法，可减少1色给中心顶点涂上。就是因为沿用此法不能导出平面图的4着色-----而偏偏是5着色。毛病出在该4个轮沿可以再继续减少颜色由4-3-最后到2（用轮图定理），这是事实。而肯普只降到3色不符合事实；当随着归纳法的继续更看出缺欠---5邻点5着色不能给中心顶点涂色；这时，若用6阶轮图定理，着色降至4。
    （2）我原文的3“阶”--阶应为“色”，您从原文出发的分析都是对的，但浪费了您的精力；我向您道歉----对不起。
    （3）关于顶点数的比较看二，i是公共顶点数，i+n是除v外图的顶点数，轮图顶点数是i+1

雷明85639720

    你说的“而我单指-----“Q构形-4邻点4着色”！用肯泊方法，可减少1色给中心顶点涂上。就是因为沿用此法不能导出平面图的4着色-----而偏偏是5着色。毛病出在该4个轮沿可以再继续减少颜色由4-3-最后到2（用轮图定理），这是事实。而肯普只降到3色不符合事实；当随着归纳法的继续更看出缺欠---5邻点5着色不能给中心顶点涂色；这时，若用6阶轮图定理，着色降至4”一段中，“而我单指-----“Q构形-4邻点4着色”！用肯泊方法，可减少1色给中心顶点涂上”，就已经达到了空出一种颜色给V着上的目的，不管这个轮是用了几色，但全图已只用了四种颜色，这就能能说明四色猜是对该图是正确的了，为什么又说它有毛病呢。“就是因为沿用此法不能导出平面图的4着色-----而偏偏是5着色”这句，不明白是如何沿用坎泊的方法“不能导出平面图的4着色-----而偏偏是5着色”呢，是否要说得明白一点。只有赫渥特说任何平面图都是5—着色的，坎泊可是没有这么说过哟。“毛病出在该4个轮沿可以再继续减少颜色由4-3-最后到2（用轮图定理），这是事实。而肯普只降到3色不符合事实。”已经给V都空出民一种颜色着上了，还要继续减少该4—轮轮沿顶点的颜色是为了什么呢。这里再继续的减少，会不会使图中别的地方会产生两相邻顶点成为同色呢。“当随着归纳法的继续更看出缺欠---5邻点5着色不能给中心顶点涂色；这时，若用6阶轮图定理，着色降至4。”这一句很不明白是什么意思。6—阶轮图实际是就是5—轮，这里不能再理解成6—色了呀。6—色轮图是什么呢。雷明

LIUFU

[这个贴子最后由LIUFU在 2013/02/02 10:10am 第 2 次编辑]

6阶轮图就是您说的5-轮。肯普没有给5邻点4着色减少颜色，但希伍德用了肯给4-轮的办法去证明了5色定理。由此更看出肯普对4-轮的办法有毛病。这“毛病”不是肯泊主观上的---虽然肯普已经给4-轮的V着上4色之1色了，肯普本人完成了可约性证明。而所有的人几乎都满足于此！这些全是肯普自己的可约性证明。朋友，我们目的要证明4色定理。为了这个目的，肯泊的方法才有了毛病。不是说他证明可约性出了毛病。这是两回事！在这里我们要想办法。还能不能用别的办法再给4- 轮减色呢？我们彼此不要急着奔向答案是什么。要慢慢去理解过程。您的预想（会不会---）是会解决的！
   用归纳法其实就是数数，可以从4开始，下面就是5；这叫陷阱。能不能从从其它开始数？星光大道就倒过来数：5,4,3,2,1！说远了。我主张用轮图定理来数数。因为那些邻点与v不就构成轮图吗！条件很充分，即有理又有据，轮图有定理为什么不去用？邻点的着色是受到轮图的约束的。

雷明85639720

朋友，如果要这么说的话，你提的问题只能是一个与着色方法有关的问题，而与证明猜测是否正确则是两回事，因为只要把已着色的轮沿顶点所占用的颜色数减少了一色给轮中心顶点着上，作为证明来说就可以说完成了，因为图中的确仍然只用了已用过的四种颜色之一。用这种着色的方法在证明猜测过程中，赫渥特已经陷入了一个“陷阱”之中，米勒也陷入了又一个“陷阱”之中了。但他们两人构造的图的确又都是可以4—着色的，只是他们不能地其进行4—着色而已。不过他们构造的两个图着色时的确也有一定的难度，所以我把他们的两个图叫做难着色图。至于两个“陷阱”是什么样的陷阱，请你等待几天，我将要发表一篇题为《着色法证明四色猜测过程中的两个陷阱》的文章，专门论述此事。至于以后还会不会有人再构造出什么构形来，他又对他的图不能进行4—着色时，又出来怀凝起目前还没有得到数学界公认的猜测是正确的结论时，那么猜测什么时候才能被证明是正确还是不正确呢。不如现在就说猜测就不正确算了，何必大家还要花那么大的气力去进行证明呢。我认为着色的方法是不能最终证明猜测的，只有走我说的不对任何图进行着色，而走用图论的方法进行证明的道路。雷明

LIUFU

[这个贴子最后由LIUFU在 2013/01/31 09:09pm 第 1 次编辑]

（1）您开头谈得很明确：“用这种着色的方法在证明猜想过程中，希伍德已经陷入了一个“陷阱”之中。您说的“陷阱”是指什么？希伍德的图是针对什么的？这里都需要具体明确指出来。因为涉及到不同的观点。我等待您的文章。
（2）我很早就赞同您不用“给具体图着色的方法”。我之所以谈“出现5色定理的根源”，宗旨是：用归纳法证明，当用肯泊给Q构形减色的方法时，也有欠缺。主张对Q构形用轮图“色数”定理来减色，它的优点是图的“色数”融入了着色。由“可着色”向“最小可着色”迈进一大步！
   如此，将不会导入5色定理这个“怪胎”！这是关键的一步！请网友特别关注它。
   百余年的症结在哪里？就在这里！

雷明85639720

好的。雷明

LIUFU

[这个贴子最后由LIUFU在 2013/02/10 02:39pm 第 3 次编辑]

带着问题学习归纳法
    为避免交流范围的扩大，我从书上抄来5色定理的证明，请大家借鉴，并试写出4色定理的证明框架。用它来学习和消化我们彼此交流的相关事宜。
一、（Heawood)任何平面图都是5-可着色的。
  证：仍设G是连通的简单平面图。设5颜色分别用1,2,3,4,5所代表，并且Vi表示涂色i的顶点，i=1,2,3,4,5.仍对n作归纳法。
（1）n<、=5时，结论显然。
（2）设n=k(k>、=5）时结论成立，n=k+1时如下证明。由定理1【1】.可知，存在v(-V(G),d(v)<、=5.设G’=G-v，则G';是k阶图，由归纳假设可知，G';是5-可着色的，下面的证明将G';还原成G时，v是可着色的。
1）若d(v)<5,v的着色无问题。
2）若d(v)=5,但与v相连的顶点在G';的着色中至多用了4种颜色，v的着色也无问题。
3）若d（v)=5,且与v相邻的5个顶点在G';的着色中已经用了5种颜色，这样v的着色就成了问题。解决办法如下。
设V1,3={V|在G';的着色中V着1或3}，并且G1,3=G[V1,3].
(a)若V1与V3属于G1,3的不同连通分支，则将V1所在的连通分支中，1,3两种颜色互换，于是V1涂颜色3，腾出1来给v着色，参见图2.（b)若V1 与 V3属于G1，3的同一连通分支，联合V形成约当曲线。对V2与V4，同理可腾出2或4给v着色。

【1】定理1：设G是简单平面图，则G中至少存在一个顶点其度数<、= 5.
二、我理解---归纳法证明之关键---是归纳假设，及如何使用归纳假设。
三、仿5色定理的证明，可试写四色定理的证明：
（1）N=、<4时，结论显然成立。
（2）设N=K（K>4)时结论成立，N=K+1时如下证明。由平面简单图知，定有顶点v，且d(v)=、<5。设G’=G-v，则G’是K阶图，由归纳假设知，G';是4-可着色的。下面的证明将G’还原成G时，v是可着色的。
1）若d(v)<4,v的着色无问题。
2）若d(v)=4,有两办法---（1）---用肯普方法，使4邻点减少一色，给v，于是原图G被修复为4可着色。---（2）由5阶轮图定理，4种颜色重新再分配：周围4点着2色，中心1色，还空1色。图G’还原为G，V是4可着色的。
3)若d(v)=5，由6阶轮图色数定理知，以v为中心的轮图是4色的，即：v的5邻点所给的4 种颜色经重新再分配，周围5点着3色，中心着第4色。图G’还原为G，v是4可着色的。
四、对留待讨论部分，欢迎广泛交流，围绕【出现5色定理的根源】
  用归纳法证明四色猜想，关键的问题就是
：在与第 n+1 面相邻的 G 的 5 个面（包括外部面）已着 4 色时，如何证明第 n+1 面也可着这 4 色中的某一色！在肯泊时代，图论的知识还不完善；现如今图论里轮图的色数定理就可以解决这个古老的问题！它不需要具体的换色过程，只用定理就可搞清结论是4可着色的。
  2月9日，我已将三补充完整，请大家发表意见。