四色猜想归纳法证明中的陷阱问题

zhangyd2007@soh

                                                             四色猜想归纳法证明中的陷阱问题

                                                                山西盂县县委党校 张彧 典
《自然》杂志 14卷 5期上刊出兰州铁道学院张忠铺教授的《数学的陷阱—— 四色猜想的各种“证明”》文章。 其中介绍了数学归纳法证明中的陷阱问题。 文中写到:
我们给出常见的错误“证明”。用 d(v)表示 v的邻点数 ,用 p表示平面图的点数。


图 1

对 p使用数学归纳法。当 p≤ 4时 ,结论显然成立。
设为 p- 1(p≥ 5)时结论成立 ,现推证为 p时结论也成立。不妨设 d ( v )= 5, v 的 5个邻点为 v 1 、 v 2 、 v 3 、 v 4 、 v 5 。再设 { V 1 、 V 2 、 V 3 、 V 4 }是 G 去掉点 v 以后的一个色分划 ,只需考虑如下两种情形。
情形 1 ：v 1 ∈ V 1 , v 2 , v 3 ∈ V 2 , v 4 ∈ V 3 , v 5 ∈ V 4 (图 1( a ) )。考虑 G 1, 3 ,不妨设 v 1 ,v 4 在 G 1, 3 的一个色分图中 ,于是存在 (v 1 - v 4 )链 ,则在 G 2, 4 中 ,不存在 (v 5 - v 2 )链和( v 5 - v 3 )链。于是把 G 2,4 中 v 5 所在色分图的点的颜色交换 (“ 2”换成“ 4”,“ 4”换成“ 2” ),使点 v 5 染颜色 2,从而点 v可染颜色 4,即为 p时结论成立。
情形 2 ：v 1 ∈ V 1 , v 2 、 v 5 ∈ V 2 , v 3 ∈ V 3 , v 4 ∈ V 4 (图 1( b ))。考虑 G 1、 3 ,不妨设存在 (v 1 - v 3 )链;考虑 G 1、 4 不妨设存在 (v 1 - v 4 )链。 从而在 G 2、 4 中不存在 (v 2 - v 4 )链;在G 2、 3 中不存在 ( v 3 - v 5 ) 链。如情形 1,可以把 v 2 换成颜色 4,把 v 5 换成颜色 3,从而点 v 可染颜色 2,既为 p 时结论成立。
综合以上两种情形 ,由归纳法原理得知 ,四色猜想成立。以上证明乍一看是对的 ,但仔细分析 , G 2、 4 中一些点换成了颜色 2, G 2、 3 中的一些点也换成了颜色 2,这些点难道不可能有相邻的?
这个证法早在 1879年就给出了 ,而现在 ,还有很多人犯这种错误。
如图 2〔1〕,用 b、 r、 y、 g表示四种颜色 ,1、 2、 3、 4、 5表示 v 的 5个邻点。有一条具有颜色 b 、 g 的 (2—— 4)链 ,也有一条具有颜色 b 、 y 的 (2—— 5)链 ,因此没有 (1—— 4)链和 ( 3—— 5)链。……由于没有 ( 1—— 4)链 ,因此可以在 G r、 g 中从 1开始交换颜色 r和 g。同样 ,由于没有 (3—— 5)链 ,因此可在 G r、 g 中从点 3开始交换颜色 y 和 r 。 但这样一来 ,相邻的点 6和 7都变成颜色 r了。 因此 ,上述“证明”是错误的。
下面 ,结合笔者多年研究四色猜想数学归纳法证明的实践谈谈对以上介绍的看法。
第一 ,图 1(b)是情形 2之 (v 1 - v 4 )链和 (v 1 - v 3 )链在 G中互不相交的简单情形 ,并没有包含图 2所示的( 2—— 4)链和 ( 2—— 5)链在 G 中相交的复杂情形这种复杂情形。 才是数学归纳法证明的陷阱。 笔者已在山西教育学院《教学与管理》1994年第 2期发表的《四色定理的数学归纳法证明》中讨论过 ,现将此种情形用图( c )或 ( d )补充到情形 2中。
第二 ,图 1(a) 和 (b)的证明没有错 ,而是十分成功的。 证法很巧妙: 作 G中某一色分图 (以 v 的某一邻点为一个端点 )的点的染色交换总是在另外两色组成的一条封闭链 (以 v 的另外两个邻点为两端点 )内或外进行 ,因此总能成功地变换 v 的这一邻点的染色 (这个过程我称为“颠倒染色程序” )而不使新染色的地图 G′发生同色冲突。
    这一成功思路就是笔者确立突破陷阱的颠倒染色程序的基础。
第三 ,文中介绍的图 2的证明 ,既不能否定图 1(a)、 ( b)的证明 ,也不能证明图 1(c)或 ( d)就没有解即四色猜想不成立。 因为证明过程出现重大分析错误从而采取了违背上述成功思路的证法。


当在图 2(1)之 (2—— 5)链外的 G r、g 中从 1开始交换颜色 r和 g后 ,原来具有 b、 g的 ( 2—— 4)链不再存在 ,因为生成具有 r 、 y 的 ( 3—— 5)链 (见图 2( 2)中粗虚线 )。
    但证明人仍然停留在未对 G r 、 g 作 r 、 g 二色交换的原图 (图 2( 1) )中考虑 ,得出“同样由于没有 (3—— 5)链的错误分析、导致在新图 (图 2( 2) )之 G r、 y 中作 r、 y二色交换 (见图 2(2)中加小括号的 ( r )、 ( y ))时 ,没有一条具有 b 、 g 的链封闭 ,从而发生“相邻点 6和 7都变成颜色 r”的同色冲突。
正确的证法是: 在图 2(1)之 ( 2—— 5)链外的 G r、g 中作 r 、 g 二色交换 (这次颠倒染色同介绍图 2的证明第一步 ) ,但生成具有颜色 r、 y的 (3—— 5)链 ,且与 ( 2—— 5)链仍呈相交情形 (如图 1(d)) ,见图 2(2)中粗虚线与粗实线所示 ,这时一定没有 ( 2—— 4)链可在 ( 3—— 5)链外之 G b、g 中作 b、g 二色交换 ,又生成新的具有 b 、y的 ( 2—— 4—— 5) 链 (见图 2(3)中粗实线 )使问题转化成类似图 1(b)情形 ,可在 (2—4—5)链内之
G r 、g 中作 r 、 g 二色交换 , 到此 , v 的 5个邻点的染色只有为 g 、 b 、 y 三色 ,可给 v 着 r 色 ,见图 2( 4)。对于图 2,经过上述三次着色调整 ,即大功告成。
上述证法就是笔者在《四色定理的数学归纳法证明》中给出的颠倒染色程序。 运用这种程序最多9次颠倒染色就可以解决四色猜想中的陷阱问题。
以上三点认识妥否? 望国内外专家评论。
注: [1]Capobianco M. MolluzzoJ. G. , Examples and Counterexamplesr in Graph Theory, North- Hel-land ( 1978)37
【特别说明】
这篇论文是在1996年，发表于山西省教育学院学报《教学与管理》第5期，这里做了部分修改。文章最后结论“运用这种程序最多9次颠倒染色就可以解决四色猜想中的陷阱问题”与我们在2022年3月发表于世界科技期刊《应用数学与物理学报》第3期上的《四色猜想中染色困局构形的4-染色》（英文）中的非十折对称染色困局构形的最多颠倒染色次数（9次）不谋而合。