我与图论1943学术讨论的记录

雷明85639720

我与图论1943学术讨论的记录
雷  明
（二○一五年八月二十八日）

我发表了我的文章《又一个证明四色猜测的好办法》（原文附后）后，有网友“图论1943”与我进行了讨论，现把我们两人的讨论记录发表于后。
图论1943提问：
我提如下5条，不一定对，供你和网友参考。
1、文中“必须去掉2条边，”最好改为“必须再去掉2条边；”。后边对应加再字。
2、文中“必须去掉n-m条边，”应改为“必须再去掉m条边。”。
3、文中（1）式没对，应为：1+2+3+。。。。。。+m=m(m+1)/2    (1)
4、由于上边的错误，所以后面的计算自然不对。
5、用此法是难成的。
我回复：
图论1943朋友：
    1、你说的文中“必须去掉2条边，”最好改为“必须再去掉2条边；”增加“再”字是对的，后边对应的都要加。
    2、但你说的文中“必须去掉n-m条边，”应改为“必须再去掉m条边。”增加“再”字也是对的，但把n-m改为m则是不对的。因为要把完全图的色数由n变成n－1时，是去掉1条边，把色数变成n－2时，是去掉2条边，那么把色数变成m时（我原文中误写成了n－m），就应是再去掉n－m条边的，而不应是m条。请朋友好好的想一想。
    3、文中的（1）式是对的，朋友，你可以推导一下。
    4、由于（1）式推导是正确的，所以后面的计算也是没有错误的。
    5、此法是否可以，有待大家共同计论，我也是看了别人的文章后有感而发的。
                      雷明。
图论1943回复：
我再说两条不一定对的意见，供雷明及其他网友参考。
    1、我的上一个帖子从第二条开始的数没和网弟雷明看的原文吻合是由网弟把数抄错了造成的。这是显然的。
    2、网弟在1楼处的原文中的第1个“必须”是对的。从第2个“必须”开始是不对的。改为“必须再”也不对。这是因为要想少用两种颜色不必去掉3条边，我们去掉两条之间没公共点的边就行了。以下同理不是必须的。我的前一个帖子说填“再”是依网弟原文得到的。
我回复：
    朋友，这本不是我的想法，是看了别人的文章后受到了启发，才在这里给大家介绍的，想与大家共同讨论。这篇文章的题目中开头有一个“93”字样，是什么意思我也不清楚。你这一贴子，我还要纠正你。比如有一个K5图，各顶均相邻，必须用5种颜色来着色。想要把色数减少到4（减少1种颜色）时，至少要去掉顶点1和顶点2间的一条边，使顶点1和顶点2着上同一颜色，这就达到了目的；如果还想把色数减到3（减少2种颜色）时，我们光是去掉了顶点1和顶点3间的一条边还是不够的，还必须再把顶点2和顶点3间的那条边同时也去掉，这才能使顶点1，顶点2和顶点3三个顶点着上同一种颜色，也只有这样才能达到使色数减少到3的目的；再往下，若想把色数再减少到2（减少3种颜色），则同样必须再去掉顶点1和顶点4间，顶点2和顶点4间，顶点3和顶点4间的三条边，才能使以上4个顶点着上同一颜色。朋友，你想想是不是这个道理呢。雷明
图论1943回复：
从这里的5楼的内容可知，你对我在4楼的话尚没细看，没理解。由于不是难明白的问题，所以我不再解释了，我认为你也没必要靠他人给你解释，你自己一认真想就能知道我说的对了。
我回复：
图论1943朋友，你的贴子我看明白了，还是感到你说的不对，人家原作者说得还是对的。你可以亲自操作一下试试看。开始我也感到原作者的这个公式有问题，后来我就亲自进行推导，发现人家的公式是没有问题的。你对我文所增加的“再”字在原作中也是有的。雷明
图论1943回复：
网弟雷明如面：
你说“人家原作者说得还是对的。”指的是那里的运算式子对还是指他的证明的路子对？请你在此告诉我。我知道你迷惑的地方后好给你解释。
我回复：
我指的是原作者的分析、推导、所得公式以及所得结论都是对的。我是如何打开了这个文章的呢，我本来想用百度搜索试找一下我的博客，我在百度搜索栏中打入“leiming1946”后，点“搜索”，出来的第一页上就有《93地图四色问题》，点开后就可以看到原作者的原文。
图论1943回复：
和此楼主说下面四条：
一、楼主处的帖子经改后把那些错误改正了，很好。
二、现在看后我认为尚有1个不足和两个错误。其中不足只原文作者有，两个错误你和原文作者都有。
三、1、不足：文中的式子推导是对的，是没问题的。这点我和你的意见一致。说“。。。。。。复杂度将相当高。。。。。。”是太小心了。
2、由于粗心，在逻辑上犯了错误。
3、同2.
四、可以说此证明是错的。现说第2条：作者和你误把必要条件当充分条件用了。况且那个条件既不是必要条件又不是充分条件了。你想想后在此说说意见。我看后再往下解释。
我回复：
1、请问你这里所说的“必要条件”和“充分条件”都指的是什么。为什么“那个条件既不是必要条件又不是充分条件了”。我们都犯了逻辑上的错误是指什么呢。
2、我又考虑了一下，感到原作者虽然对公式的推导没有问题，但这只是从完全图角度出发的，最后剩下的仍是一个完全图，是一个m＝4的完全图，并不是任意的平面图。尽管m≤4 的完全图的色数都不大于4，但它却不能代表任意平面图的色数也都不大于4。所以原作者最后的结论应该说是对的，因为它还不能证明任意平面图的色数都不大于4。但原作者认为还不能证明四色猜测是正确的原因却是不对的，其原因则应是我上面所说的。你上一贴中的第一条中所说的是对的。朋友，你看我现在的认识是否对呢。
图论1943回复：
网弟：
1、你14楼的帖子几乎完全对了。只有一处没说太确切，即最后剩下的应是K4和（n-4)个散点，不应只有K4.你现在的认识是完全对的。
    2、我是家里各方面（含采购、做饭等）的一把手，时间紧。我是网友中上网能力最差（低）的，打字又是最慢的。所以，我原想下狠心用较长时间也要把此证法不对和你说明白。现在看来，你的理解能力、分析问题能力太强了，三、五天不用画图（因我不会在网上画图）只用汉字我就能把此证明的错误向你说明白（令你明白）。
    3、首先说“必要条件”和“充分条件”的概念就是中学数学书里的概念。对此需举例说明的话，告知，我就举例说明，不需说明的话，告知，我就抽空往下说。
我回复：
1、朋友：你的第一点说得非常的对，我忘掉了还有n－m个孤立顶点。我不是问你必要条件与充分条件的定义，而是问你在作者的原文与我的文中，指那些是必要条件，那些又是充分条件呢。
    2、朋友，你所说的必要条件和充分条件是不是指的e＝3v－6呢。还是原作者的公式呢。
网友太平天下回复：
点击可看〈93地图四色问题〉！本人水平低下，只是觉得，该文好象还没有证明四色问题吧？……
我回复：
太平天下朋友，我与图论1943正在讨论这个问题呢。这两天我又好好的考虑了一下，的确也感到了这一问题。我在回复图论1943时已经说到了，原作者这里只是从完全图（图的一种类型）出发，并没有得出在任意的平面图时，四色猜测是正确的。我将对我的文章进一步修改，改变题目，重新发表在这里。
太平天下朋友，你是否可以把《93地图四色问题》一文中的第二个证明找一下，教给大家打开的方法，以便大家更好的去研究它。
图论1943回复：
    依网友太平天下在此17楼处发的帖子使我方才看到了原文。由于我的知识面窄、少，所以有些地方我没看懂。我认为原文确实有错误。我看它的定理4就不对。今举一反例供网友太平天下、雷明及其他网友参考。若是我错了，请及时在此告诉我。谢谢了。
     反例：设点数n=8,颜色种数m=4,边（线）数e=18,满足关系：e不大于3n-6.再设此8个点用A1、A2、A3、A4、A5、A6、A7、A8来表示。今令前6个点构成K6.则K6占用了15条边（线）;A1和后两点A7、A8构成K3，K3占用了3条边；至此18条边都安排完了。显然此形（当然是三维空间里的啦。）用4种色就不够用，至少有6种颜色才行。由此可见那里的定理4是错的。
    网友太平天下使我能看到了原文。我谢谢太平天下了。
我回复：
朋友：
    1、在回复你的这一贴之前，先对回复你的上一贴的回复进行一下更正。通过操作，原作者那个图最后剩下的是一个Km团和n－m个顶点，但这些顶点并不是孤立顶点，而是每个顶点都是与那个Km团中有m－1个顶点相邻的、实际上就是n－m个K（m－1）团。当m＝4时，就只是剩下一个K4团和n－4个K3团。由于图中含有K4团，所以其色数一定会是4。
    2、原作者对他的那个公式的推导应该说还是正确的，只是觉得好象该公式对证明四色猜测没有什么用处。你所举的例子与人家所说的不太相同，当然就得到了不同的结果。仍以你的8个顶点为例，按原作者说的应是一个非平面图的K8图，共有8×7＋2＝28条边，两两顶点间均有边相邻，着色时得用8种颜色。当把顶点1与顶点7间的边去掉时，就可以用7种颜色着色了，顶点1和顶点7用同一种颜色；再把顶点1与顶点8间的边去掉，并把顶点8与顶点7间的边也取掉时，就可以用6种颜色着色了，顶点1、顶点7和顶点8三个顶点用同一种颜色。这时图中才取掉了3条边，还有25条边，是大于3n－6＝18的，这时的图还是一个非平面图。而你所说的8个顶点的图中只有18条边，且含有一个K6团，占去了6×5＋2＝15条边，剩下的3条是连接着顶点1、顶点7和顶点8的K3团的3条边。由于这个图中含有K6团，仅管图中总边数是不大于3n－6＝18的，也是一个非平面图，是不可能用4种颜色来着色的，其色数必然是图中最大团K6的顶点数6。原作者说的去掉了的顶点1、顶点7和顶点8间的3条边，在你的图里却正好是连接着这3个顶点的3条边。你的说法是不符合原作者的本意的，所以你的结论是错误的。
    3、关于该公式，我还有别的分析来说明它不能用以证明四色猜测的，由于时间太晚了，就等明天再说吧。本来我想把我的文章早点删掉，现在就只好等和你讨论完了后再删吧。
图论1943回复：
    回复雷明：你说（n-m)个点并不是孤点是对的，说它们散仅指它们之间散，散到一条边也没有。它们每个点都和剩下的m个点相邻。当m=4时，剩下的是一个K4，此时能构成（n-4)个K5，但一个K6也构不成，此图需5种色。当m=3时才是需4种色的。
我回复：
几个所谓散点都与那个Km团中的m－1个顶点相邻，不是与m个顶点都相邻。当m＝4时，K4有4个顶点，着色时就须要4种颜色。这一点你好好地想想。
图论1943回复：
回复20和22楼的帖子：1、20楼的第1条和22楼的内容是同一个。对此内容我希望你自己再核对一次。2、对20楼的第2条说我不符合作者本意。哪不符合呀？你也没具体说出来呀！另外我是针对定理4说的。你看看我符不符合定理4的条件吧。
我回复：
1、朋友，我不是用你的那个有8个顶点的图，把原作者的思想和你的思想都举了例吗，那样说明还不叫具体，那什么叫具体呢。你的操作没有按原作者的思路来，这就叫不符合原作者的本意。原作者的定理4也是按他的操作最后得到的，定理4是与他的操作相同的。对于按作者的操作最后得到的图的最大团到底是Km，还是K（m＋1），请你再想一想。比如你说的当m＝4时，图中还有n－m个K5团，而我认为是还有n－m个K3团。请你再操作一次吧。我两次给你说的操作都是相同的，结果也应是一样的。
    2、朋友，原作者的定理4的解释的第2条中是不是少了“平面图”三字，很显然，不是平面图的图，绝大部分的色数都是大于4的，但也有个别图是例外的，比如非平面图K3，3图的色数就是2。由于这个原因，你才能举出你昨天的那个有8个顶点的例子，你说的那个图本身就是一个非平面图，当然是不能用4种颜色来着色的。
    3、朋友，关于原作者的定理4中当m＝4时，e≤3n－6（该式为平面图中的最大边数，也是判断一个图是不是平面图的标准）是否偶然的问题，原作者认为决非偶然。原作者的理由我还没有看明白，我也说不上来是否是偶然的，但我知道，亏格为0的平面图的最大边数是e≤3n－6，而亏格为1的非平面图的最大边数是e≤3n，亏格为2的非平面图的最大边数是e≤3n＋6，等等。亏格为1时顶点最多的完全图是K7，其着色必须用7种颜色，但原作者的定理4中当m＝7时，所剩边数e并不是等于3n。这样看来原作者的定理4在m＝4时，e≤3n－6是纯属偶然导致。它并不象我用欧拉公式直接推导出的赫渥特的多阶曲面上的地图着色公式那样，在亏格为0时色数是小于等于4的，而在亏格为1时，色数是小于等7的，这与与实际是相符的。雷明
图论1943回复：
你在此27楼处的回复完全对。下边我们说你在22楼处和在20楼处的第1条说的那个问题。设n=8；对应完全图K3，由3个散点（之间一条边也没有的3个点构成的集合。）记为（K3).(K1)、(K2)、（K4)等的含意自明了。8个点同前所设为A1、A2、A3、。。。A8.
    1、去掉A1和A2之间的边得（K2),余下的那6个点构成K6.此时A1和K6里的6个点（即后6个点）都相邻，故此7点构成了K7.同理A2也和K6构成K7.但此时构不成K8是显然的。因A1和A2可同色，所以共需7种色。
    2、再去掉A3和前两点间的边，得（K3),余下的5个点构成了K5.此时A1和K5里的5个点都相邻，故构成了K6.同理A2、A3也都能分别和K5构成K6.因（K3)里3个点可用一种色，所以共需6种色。
    3、再去掉A4和（K3)间的3条边得（K4),余下的构成K4.类似可构成4个K5.需5种色。
    4、再去掉A5和（K4)之间的4条边，得（K5),余下的构成K3.类似构成5个k4.共需4种颜色。至此，你该知道你在那两处说得对不对了。
我回复：
1、纠正你一个概念，之间没有一条边的所谓三个散点就是三个散点，不能叫作K3团，K3是指三个顶点间均相邻的顶点，不但有三个顶点，还有三条边的。你使用术语时应尽量与图论上已有的术语保持一致，这样大家都容易明白。
2、我好好的看了一下，你和我说的都是对的。我是认为去掉一条边后，剩下的是一个K7，这个K7外只有一个所谓的散点，这个散点也是一个K7中的一个顶点，它却只与前一个K7中7－1＝6个顶点相邻；而你却认为去掉一条边后，剩下的是一个K6，这个K6外有两个所谓的散点，这两个散点都与那个K6中的6        个顶点全相邻，也构成了两个K7。
3、我看我前面说的是没有错的，你若还认为有的话，就请直接指出来。
图论1943回复：
网友雷明：不需要我在网上说明那篇文章在逻辑上的错误了吧？
我回复：
你不说我怎么能知道呢，就是你说的“那篇文章”我也不知你道底说的是哪一篇呢，是《93地图四色问题》呢，还是我的哪篇文章呢。我从来不会嫌别人指出我的文章的具体错误的，但我若认为不错时，我还是要辨论的，还是会坚持的。不指出具体问题只是反对、批评、指责，那是不行的。
图论1943回复：
我指的是“93地图四色问题”。
我回复：
关于《93地图四色问题》一文中逻辑上的问题，我还没有看出来，你认为在这里还是在邮箱中那里合适你就在那里讲，以达到相互交流的目的。

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

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


附：我的文章《又一个证明四色猜测的好办法》：

又一个证明四色猜测的好办法
雷  明
（二○一五年八月二十五日）
    我昨天在网上看到一篇题为《93地图四色问题》的文章，好象是“国强”写的，但文章下面没有署名，“国强”和“GuoQiangL”的博客中也没有看到这篇文章。
该文中提到一个顶点数为n完全图的边数是n（n－1）/2，着色时需要n种颜色。当该图要用n－1种颜色着色时，必须去掉1条边，要用n－2种颜色着色时，必须再去掉2条边，……，直到要用m种颜色着色时，必须再去掉n－m条边，这时图中一共去掉的边数是
        1＋2＋3＋……＋（n－m）＝（n－m）（n－m＋1）/2                   （1）
这时图中所剩的边数是
        e＝n（n－1）/2－（n－m）（n－m＋1）/2
         ＝（m－1）（n－m/2）                                                   （2）
当m＝4时，（2）式则变成
        e＝3n－6                                                                   （3）
这就是顶点数为n的平面图的最大边数公式。当m≤4时，（3）式则变成
           e≤3n－6                                                                  （4）
这就是顶点数为n的任意平面图的边数公式，也是判断一个图是否是平面图的条件。
    作者的结论是：故可用4种颜色为任一个平面图着色。至此，地图四色定理已得到说明。
    我也同意这种观点和证明方法。但作者最后却说：“这种方法的难以突破的关键在于公式（2），若能严密的证明公式（2），就给出了地图四色定理的精确证明。但上文只对公式（2）进行了表象上的说明，仅仅是经过有限次的逐次推导说明了一下公式（2）的正确性，事实上只证明了公式（2）在m=n－1, n－2等的时候成立，而若对任意的m用数学归纳法等初等数学方法精确证明公式（2），其复杂度将相当高。需借助其它工具进行。故此法方仍有待考究。”
    我认为作者以上对公式（2）的推导过程就应该说是证明过程，只要推导过程没有问题，这个公式也就应该没有问题，不需要再进行证明了。应该说四色猜测也就得到了证明是正确的。即任何平面图都可以用不多于四种的颜色来着色。比如我们已经用配方法推导出的一元二次方式的求根公式，还需要再进行证明其正确与否吗。不需要了。
    这位作者，我支持你的观点，支持你的证明方法。
另外你后面还说有一个“利用代数中全集、子集的概念和数学归纳法原理来说明四色定理”的证明方法，但文中却没有这一部分的内容，请作者能及时把它也发表在《中国博士网》上，以供网友们共同讨论。

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