简评四色定理的一种非计算机“逻辑证明”

杨 军，李高平，李 庆

(西南民族大学数学学院，四川 成都 610041)

四色猜想(The Four Color Conjecture，4CC)、Fermat猜想、Goldbach猜想和Riemann假设是学界公认挑战人类智商的四大世界数学难题[1-2].其中4CC是指平面图的色数不超过4，即任意地图均可用四种颜色进行着色，使得有共同边界的区域着色不同.虽在1976年Appel和Haken采用寻找可约的不可避免构形集的方法，利用计算机辅助计算宣布证明了4CC，但证明过程太长，以至于无法手工验证，故有些人从根本上反对使用计算机，迄今为止不少图论学者(爱好者)仍在寻找攻克4CC的简洁纯数学(非机器)证明[3-5].2020年，Y.Wang[6]基于Kempe提出的构形(configuration)和可归约性(reducibility)概念提出了一份4CC的归谬法证明(以下简称WK-证明).虽历史上Kempe方法被Heawood在1890年成功运用到五色定理的证明，但1879年Kempe在4CC“证明”过程中最小度δ＝5的情形因无法证明可归约性而遭遇11年之后Heawood图的反例攻击[2，7].于是，Y.Wang尝试将Kempe“证明”中的核心概念“最小图”改为基于临界5色图的存在性.本文对此展开若干比较性研究，提出评价及建议.

1 预备知识

定义1[2，5]：若图G存在平面图形表示使它的边仅在端点处相交，则称G为可平面图(planar graph).G的这种图形表示被称为平面图(plane graph)

定义2[4，8]：平面图G被称作极大平面图(maximal plane)，若不能添加新边形成平面图G"⊃G，且从直观上等价地看，它是指在任意一对不相邻的顶点之间添加一条边便可破坏其平面性的平面图.

定义3[2，8]：图G＝(V，E)的一个顶点着色(vertex coloring)定义为一个映射

c：V→S(颜色集)，使得任意两个相邻的顶点v和w均有c(v)≠c(w).当基数时，称G拥有一个k-着色(k-coloring).参数χ(G)＝拥有k-着色}被称为G的点色数((vertex-)chromatic number)，简称色数.当χ(G)＝k，称G是k-色的(k-chromatic)；当χ(G)≤k，称G是k-可着色的(k-colorable).

定义4[2，9-11]:设χ(G)＝k≥2.若对任何真子图H⊂G，均有χ(H)＜k，则称G为临界k-色图(criticalk-chromatic graph)，简称为k-临界图(kcritical graph)[5，7].

定义4[6]:一个k-色图被称为临界的(critical)，若任意删除一个顶点或一条边后总得到一个色图.

定义5[2，12]:若有平面简单图G满足χ(G)＝5，但对于任何阶小于图G的阶ν(G)的平面图H均有χ(H)≤4，则称G是最小图(minimal graph).

(Heawood)五色定理[5，8]:任何可平面图都是5-可着色的.

2 WK-证明:概述

采用归谬法证明.若4CC不真，则在可平面图中应该存在若干5-色图.令G是一个临界5-色图，则最小度δ(G)＝4，5.

情形一:当δ(G)＝4，置G的顶点u的度数degG(u)＝4.令u的邻点集

如图1所示.

图1 deg G(u)＝4Fig.1 deg G(u)＝4

图2 若边v1 v2消失，则该图能变成4-可着色图Fig.2 If the edge v1 v2 is missing，the graph can become 4-colorable.

边v1v2，v2v3，v3v4，v4v1存在的理由是假如它们中的任意一个消失，比如v1v2消失，那么通过组合v1和v2成为v12的图就是图2中的G".因为G"的边数小于G的边数，所以G"应该是一个4-可着色图.在此情形下，只要G"被变回到G，我们就能够得到4-可着色图G，这与G是一个临界5-色图的假设相违.其余部分及情形二(当δ(G)＝5)，详见文献[6]原文.

3 简析WK-证明失效的原因

首先指出，虽有四色猜想(The Four Color Conjecture，4CC)之说，但WK-证明中的5-color graph及4-colored graph均属非专业术语.从其上下文看，应分别改为5-色图(5-chromatic graph)及4-可着色图(4-colorable graph)这两个概念.下面我们针对WK-证明提出4点分析.

第一点，定义4"值得商榷.下面我们举一反例比较定义4和定义4".

图3 C3的一个删点删边运算Fig.3 An operation of deleting a vertex and an edge

由图3可知，奇圈C3是3色图，而其子图C3-v1阶完全图K2的补图)是1色图.根据定义4及性质[2]“G是临界3色图⇔G是奇圈”，知C3是临界3色图.另一方面，根据定义4"，我们针对C3设计一个删点删边运算，使得产生的子图K c2的色数

由此推出“C3不是临界的”的谬论.故我们建议放弃定义4"而回归到定义4.

第二点，四色猜想的研究范畴属于极大平面图[1，8]，但文献[6]并未阐述其关联性，故我们运用极大平面图审视WK-证明过程.断言：图1只是临界5-色图G的一个子图G"，但并非极大平面图.证明如下：利用极大平面图的一个特征[2]设G是v(≥3)阶简单平面图，则G是极大的⇔ε＝3v-6.在G"中，ε＝8，v＝5，不满足ε＝3v-6，故简单平面图G"还不是极大的.

图2 的左侧子图是多余的，因通过实施删除新生的平行边、环及孤立点的“边收缩”运算[2，8-10，12]直接从图1即得图2的右图(边收缩图G.e，其中边e＝v1v2)，且G.e已进化成为极大平面图(因ε＝6，v＝4满足充要条件ε＝3v-6).

在图论中没有“把点v1和点v2组合成为点v12”的运算，应改为上述“边收缩”运算.同时在此谨需指明一个“一词多义不等价”的图论特有现象：也有部分文献，如文献[5，7，13，14]并不删除“边收缩”运算诱导出来的平行边.

第三点，在WK-证明中把“最小图”改用“临界5色图”并作为归谬法的起点假设，我们评价这是其最大的逻辑“硬伤”.理由1[7，10]：每个k-色图G均有一个k-临界子图(k-critical subgraph)H，但未必有G＝H.理由2[2，5]：对于色数k≥4，人类迄今尚未找到临界k-色图的特征(即充要条件).我们认为，这是人类尚未发现4CC纯数学证明在基础研究平台上的一个瓶颈原因.理由3[2，12]：根据5色定理可知，若4CC不真，则必存在最小图.这可能是文[6]认定“令G是一个临界5-色图”的依据，但我们指出：最小图≠临界5-色图(二者的共性是5-色图，但最小性的主体对象不同：前者指“图的阶”，后者指“点色数”).因此，我们质疑WK-证明的做法产生了如下的逻辑二难困境：若按“临界5色图”处理，则其存在性当今图论无法保证；若按最小图对待，则疑似遭遇传统的Heawood图的反例攻击.事实上，不同于最小度δ＝4的安全情形，WK-证明对于有逻辑失误风险的δ＝5情形反而欠缺完整细节.倡议4：在探索世界级数学难题时，应防止某些学者打着“不妨假设；同理可证；可以证明”的旗号实施“我断言，你验证——信不信由你”的行文策略；正因为是世界级数学难题，一般读者不能直接验证或间接补充.故无论证明或算法的复杂度多高，严谨负责的做法是提供完整的对应附件(若长).我们认为，这是人类挑战机器证明必须付出的智慧代价.巧合的是，WK-证明全程使用了4次“应该是”(should be).对此我们再次倡议：针对数学猜想的正式证明不能抱持“猜”的态度或方法.

第四点，WK-证明采取“反证法中的反证法”的思路本身是合理合法的，但即使把原文中的anyone(任何一人)改为any one(任何一个)，后面的推理仍然违背了逻辑否定的De Morgan律(全称量词∀与存在量词∃的互换).WK-证明在图2中用反证法证明断言“(所有的)边v1v2，v2v3，v3v4，v4v1都在G中存在”；该命题的否定应为“存在某一条边(基于在图1中这4条边关于G的最小度顶点u具有(在同构意义下的)中心对称性，故不妨设)v1v2，满足v1v2∉E(G).”这是一种常见、可救但必改的逻辑bug.

4 结语与展望

(1)我们的反例表明：WK-证明中使用的新定义4"有缺陷，应首先回归到标准定义4.

(2)最近一项研究成果[1]业已揭示Kempe不能证明4CC的根本原因：Kempe变换不能从一个4-着色导出所有的4-着色.我们的对比分析结果表明：把Kempe“证明”中的核心概念“最小图”改为“临界5色图”的做法产生了如下的逻辑二难困境：若按“临界5色图”处理，则当今图论无法保证其存在性；若按最小图对待，则原文尚缺论证能够抵抗传统的Heawood图的反例攻击.

(3)展望：视围棋比赛为一系列2色顶点动态演化(单点增加与多点删除运算)的图变，从近年“围棋人机大战”(指人工智能围棋程序AlphaGo成功挑战两名世界顶级围棋大师李世石及柯洁)得到启示：在大数据、网络通信与人工智能融合发展的新时代，除非为了锻炼“思维的体操”，追求纯粹数学难题的解决方案不宜囿于裸脑思维与手工操作的原始心态与自娱方式，而应与时俱进地接纳/采取基于计算机算法的辅助证明模式，如文献[15].采用手工检查计算过程的专家们逐步积累并已达成共识[5]：在数学证明中犯错误的概率远远大于在算法正确性得到证明的情形下计算机犯错误的概率.故我们预测，在已经拥有4CC人机合力证明的客观实情下，主观探索4CC的纯人工证明工作或将被倒逼成为一个“品质更高(包涵正确性、可读性、简洁性和数学美)的买方(喻指读者群)市场”.最后期望，一方面关注近年4CC纯数学证明的若干新视角、新途径，如与4CC密切相关的整数流和子图覆盖[16，17]、在极大平面图理论架构下从图计数的角度[1，4]来寻求证明4CC.另一方面，超越趣味数学游戏精神的初心，寻求现实世界里有广度和深度的衍生实用，任重道远.