[交流] 介绍四色问题的肯普证明（节选自《数学证明》、大连理工大学出版社 著 萧文强）

为方便朋友们的学习,下面将《数学证明》（大连理工大学出版社，著  萧文强）一书中有关肯普的错误证明介绍给大家. 要明白肯普的证明错在哪里与后来希五德怎样修正,较清晰地叙述是采用普通的图论语言.一个图由某些点和相连其中一些点的边组成,每个点的次数是以该点为一个端点的边的数目.如果每两点顶多只有一条边相连,又没有一点自己与自己有边相连,这个图叫做单图.如果任意两点必有一条点接点由若干条边合起来的路线连着,这个图叫做连通图.如果全部点和边都在一平面上,而且任意两条边没有相交点[端点不计],这个图叫做平面图.平面图的边,把平面分为若干份,每份叫一个面.设有v个点,e条边和f个面,著名的殴拉公式v+f-e=2把这三个数字联系了起来.设平面图是单图且为连通图,则可证明必有一点的次数不大于5.利用反证法:设若不然,则每点的次数均不小于6,即:6v<=2e.同时又由于每个面至少有三条边,即:3f<=2e.将两式代入殴拉公式得:2<=e/3  + 2e/3 - e = 0 ,产生矛盾!所以一个单且连通的平面图必有一个点的次数不大于5.作:deg<=5. 给定一个地图在每个国家里取一点,若两个国家有共同a/b/c/d(图1).观察所有以v'为起点,点接点由若干条边组成的路线,上面的点隔个涂上a和 c.如果没有一条这样的线路以v'"为终点的话,我们只用把这些路线上的a和c两色互调,便可以把v'的色改为c,仍维持四种颜色着色，把 v 涂上a色补回去,便知道原来的图只需要四种颜色,与图的选取产生矛  盾(图1).                                                  如果从v'至v'"有一条这样的路线,便不可能从v"为起点,有一条点接点由若干条边组成的路线,上面的点隔个涂上b和d,终点是v"".于是用类似的推断,亦产生矛盾(见图2)! 情况2:v的次数是5,与v相连的五点v'/v"/v'"/v""/v'""各涂上色a/b/a/c/d(见图3).像刚才的考虑一般,可以假定有一条点接点由若干条边组成的路线,从v"走到v'"",上面的点隔个涂上b和d,也有一条点接点由若干条边组成的路线,从v"走到v"",上面的点隔个涂上b和c.于是从v'至v""不会有这样的路线,上面的点隔个涂上a和c;从v'"至v'""也不会有这样的路线,上面的点隔个涂上a和d.把这些从v'出发的路线上的a和c二色互调,把这些从v'"出发的路线上的a和d二色互调,便可以把v'与v'"的色分别改为c和d,于是把v涂上a色补回去,便知道原来的图只需用四种颜色,与图的选取产生矛盾! 肯普以为他排除了全部可能情况,所以没有找到反例.即是说,四色猜想给证实了.希五德指出的漏洞出现于最后一种情况,当我们把那些从v'出发的路线上的a和c二色互调时,可能制造了一条从v'"至v'""的路线,上面的点隔个涂上a和d!(v'"-d-c-v'"" 因此,当我们再把a和d二色互调时,只是把v'""的d色换作d色,把v'"的a色换作d色,对v来说仍然要涂上第五色!他给了一个反例(见图3).固然这是一个局部反例,说明了原来的证明行不通,却不是全局反例,因为他的图(*)是可用四种颜色着色的.希五德还指出肯普的想法,可以搬来证明五种颜色是足够了,读者愿意试证明吗? 肯普的想法虽然行不通,却是一个很有意思的想法.他的战术是找出一组"无可避免"的构形,意思是说任何单且连通的平面图肯定包含至少一个这类构形作为里面的一部分,然后设法证明每一个这类构形都是"可约"的,即它不能在四色猜想的最小反例里出现.肯普的证明所选的"无可避免"的构形,由那些次数小于5和它的相邻点组成,他以为已经证明了每一个都是"可约"的,但希五德指出了最后一个并不是"可约",故证明不完全.后来从事这方面研究的人还是循着这条路走,把那些并不"可约"的"无可避免"构形再分解,试图证明分解了的构形变成"可约"的.这样做可能导致一组个数很多的"无可避免"的构形,曾经一度大家以为约有一万多个,其中有些还包含很多点的,即使运用电子计算机去验证一个这样的构形是否"可约",亦得花上100个小时.撇下储存问题不理,单是计算也得花上100年左右!后来美国数学家哈肯与阿佩尔成功地把"无可避免"构形数缩减至1478个,把验算时间缩短至1200小时.在1976年,他们宣称四色猜想是对的.文章在1977年发表,长达139页,还附上电子计算机程序的微形胶片400页!过了10年后,还有人对他们的证明提出质疑,认为存在着漏洞.哈肯与阿佩尔亦有回应.据他们说,那些漏洞都给补足了.对于四色猜想是否解答了,数学家的意见还是莫衷一是. 四色问题由肯普的证明至今已一百多年,究竟有多少人研究过他的方法,又有多少人亲自动手去操作实践一下他的方法的过程,不得而知.请有意为学之精神者认真读书.这是我亲自从萧教授的书上节选的,保证无误.并希广泛发表意见,以鼓励本人继续学习. *这里的图指原书希五德举出的反例图,该图是块地形图,在电脑中很难画.故本人经认真分析研究后选取用图3表示.根据最少着色原则,他所举的图例可用四种颜色着色. 有关的图另发。

回复此楼