2021年5月第47卷第3期
西南民族大学学报（自然科学版）
Journal of Southwest Minzu University ( Natural Science Edition)
M a y.2021
Vol.47 No. 3
doi ：10. 11920/xnm dzk. 2021. 03. 013
杨军，李高平，李庆
摘要：2020年，Y.W a n g基于构形和可归约性的经典概念提出了一份四猜想（T h e F o u r C o l o r C o n j e c t u r e J C C)的归谬法证明.首先构造反例指出其“临界A'图”定义的一个缺陷.其次对比分析表明，把“最小图”改为“临界5图”的做法产生了逻辑二难困境：若按前者对待，则原文尚缺论证能
够抵抗传统的H e a w o o(丨图的反例攻击；若按后者处理，则当今图论无法保证其存在性. 关键词：四猜想；极大平面图；最小图；临界A.-图；H e a w o o d图 中图分类号:0157.5 文献标志码：A文章编号:20954271(2020 )06*0326>04
A brief comment on a non - computer "logical proof" of the four - color theorem
YANG Jun, LI Gao - ping, LI Qing
(School of Mathematics, Southwest Minzu University, Chengdu 610041 , China)
Abstract ： In 2020, Y. Wang proposed a proof by contradiction of the Four Color Conjecture (4CC) based on the two classic concepts of configuration and reducibility. This article first constructs a counterexample to point out a defect in the definition of "critical 5 - chromatic graph" . Secondly, the comparative analysis shows that the practice of changing the "minimal graph" to the "critical 5 - chromatic graph" has begot a logical dilemma：If it is treated as the former, then the original still lacks the proof that it can resist the counterexample attack of the traditional Heawood graph；if it is dealt with as the latter, then the contemporary graph theory cannot guarantee its existence.
Keywords：Four Color Conjecture (4CC) ；maximal plane graph；minimal graph；critical h - chromatic graph；Heawood graph
四猜想（The Four Color Conjecture，4CC)、Fer-mat猜想、Goldbach猜想和Riemann假设是学界公认 挑战人类智商的四大世界数学难题其中4CC是 指平面图的数不超过4，即任意地图均可用四种颜 进行着，使得有共同边界的区域着不同.虽在 1976年Appel和Haken采用寻可约的不可避免构 形集的方法，利用计算机辅助计算宣布证明了 4CC，但证明过程太长，以至于无法手工验证，故有些人从 根本上反对使用计算机，迄今为止不少图论学者（爱 好者）仍在寻攻克4C C的简洁纯数学（非机器）证 明|3-5].2020年，Y.Wang[6]基于Kempe提出的构形(configuration)和可归约性（reducibility)概念提出了 一份4CC的归谬法证明（以下简称WK-证明）.虽历 史上Kempe方法被Heawood在1890年成功运用到五 定理的证明，但1879年Kempe在4CC“证明”过程 中最小度5 = 5的情形因无法证明可归约性而遭遇 11年之后Heawood图的反例攻击[2’7'.于是，Y.Wang 尝试将Kempe“证明”中的核心概念“最小图”改为基 于临界5图的存在性.本文对此展开若干比较性研 究，提出评价及建议.
收稿日期:202(M39>09
作者简介：杨军(1963-)，男，汉族，重庆涪陵人，教授，博士.研究方向：信息安全与密码学、数学建模.E-mail:jimyang898@ m
基金项目：国家自然科学基金青年基金项目（11401493)；西南民族大学中央高校基本科研业务费专项资金项目（2020N Y B 17)
第6期杨军，等：简评四定理的一种非计算机“逻辑证明327
1预备知识
定义1[2’5]：若图C存在平面图形表示使它的边 仅在端点处相交，则称C为可平面图（planar graph). C的这种图形表7K被称为平面图（plane graph)定义2[4’8]：平面图C被称作极大平面图（maximal plane) ，若不能添加新边形成平面图 G D C， 且 F(C)= V(C).从直观上等价地看，它是指在任意一 对不相邻的顶点之间添加一条边便可破坏其平面性 的平面图.
定义3[2’8]：图C= (K, £)的一个顶点着(vertex coloring)定义为一•个映射
C: S(颜集），使得任意两个相邻的顶点和均有C(1；)#当基数|S|= A：时，称G 拥有一个 A -着（A - coloring)•参数;G)= m inU:G拥有A:-着}被称为C的点数（（vertex -)chromatic number)，简称数.当;^(G)= &，称 G 是 i-的（A: - chromatic)；当;G) ^，称 G是 i - 可着的(A：-colorable).
定义4[2_9-"]：设;^(c)= A 2 2.若对任何真子 图//C G，均有尤（//)<1则称C为临界图(critical A:- chromatic graph)，简称为 A:-临界图（4-critical graph) [5,71.
定义4 [6]:—个A -图被称为临界的（critical), 若任意删除一个顶点或一条边后总得到一个(A - 1)- 图•
定义5[2’12]：若有平面简单图C满足;^G)= 5, 但对于任何阶小于图C的阶〃（C)的平面图W均有 尤(//) <4，则称 G是最小图（minimal graph)•
(Heawood)五定理U_8]：任何可平面图都是5 - 可着的.
2 W K-证明：概述
玻璃钢酸洗槽采用归谬法证明.若4CC不真，则在可平面图中 应该存在若干5 -图.令C是一个临界5 -图，则 最小度5(G)= 4, 5.
情形一：当S(C)= 4，置C的顶点u的度数 deg c(u)= 4.令u的邻点集
/vc( «) = i v t , v2, v3, ■
如图1所示.
V3
V1
图1degf;( u) = 4
Fig. 1deg6( u) = 4
V3V3
图2若边消失，则该图能变成4-可着图
Fig. 2 If the edge vxv2is missing,
the graph can become 4 - colorable.
边¥2, ¥3, C i存在的理由是假如它们
中的任意一个消失，比如消失，那么通过组合
无纺布储物箱和巧成为〃12的图就是图2中的C'因为G的边数小
于C的边数，所以C'应该是一个4-可着图.在此
情形下，只要C被变回到C，我们就能够得到4-可
着图C，这与C是一个临界5-图的假设相违.
其余部分及情形二（当3(C)=5)，详见文献[6]原
文.
3简析W K-证明失效的原因
首先指出，虽有四猜想（The Four Color Conjecture， 4CC )之说 ，但 WK- 证明中的 5 - color graph及 4 - colored graph均属非专业术语.从其上下文看，应 分别改为5 -图（5 - chromatic graph)及4 -可着 图(4-colorable graph)这两个概念.下面我们针
对
328西南民族大学学报（自然科学版)第47卷
评1^-证明提出4点分析.
第一点，定义4'值得商榷.下面我们举一反例比 较定义4和定义4 .
vi
长为3的圈C3
图3 C3的一个删点删边运算
Fig. 3 An operation of deleting a vertex and an edge
由图3可知，奇圈(：3是3图，而其子图C3 - a
g (2阶完全图&的补图）是1图.根据 定义4及性质[2]“C是临界3图e C是奇圈”，知 C3是临界3图.另一方面，根据定义4'，我们针对 C3设计一个删点删边运算，使得产生的子图g的 数水泥锥
火（g) = 1# 3 -1= 2.
由此推出“C3不是临界的”的谬论.故我们建议 放弃定义4而回归到定义4.
第二点，四猜想的研究范畴属于极大平面图[1’81，但文献[6]并未阐述其关联性，故我们运用极 大平面图审视WK-证明过程.断言：图1只是临界5 -图C的一个子图G，但并非极大平面图.证明如 下：
利用极大平面图的一个特征[2]设6是〃（23)阶 简单平面图，则G是极大的<=>£ =3v-6.在G中，e =8,z； = 5 ，不满足占=3t； -6，故简单平面图G还 不是极大的.
图2的左侧子图是多余的，因通过实施删除新生 的平行边、环及孤立点的“边收缩”运算[m|2]直接 从图1即得图2的右图（边收缩图C.e，其中边e= )，且C.6已进化成为极大平面图（因£ = 6,t; =4满足充要条件s= 3v - 6 ).
在图论中没有“把点h和点h组合成为点〃12 ”
的运算，应改为上述“边收缩”运算.同时在此谨需指 明一个“一词多义不等价”的图论特有现象：也有部分
文献，如文献[5,7，13，14]并不删除“边收缩”运算诱 导出来的平行边.
第三点，在WK-证明中把“最小图”改用“临界 5图”并作为归谬法的起点假设，我们评价这是其 最大的逻辑“硬伤”•理由1[7’1<)]：每个A-图C均有 一个A:-临界子图（A:- critical subgraph)//，但未必有 C= //.理由2 2’5]：对于数A 2 4，人类迄今尚未 到临界A-图的特征（即充要条件）.我们认为，这是人类尚未发现4CC纯数学证明在基础研究平台 上的一个瓶颈原因.理由3[^|2]：根据5定理可知，若4CC不真，则必存在最小图.这可能是文[6]认定 “令C是一个临界5 -图”的依据，但我们指出：最 小图
#临界5 -图（二者的共性是5 -图，但最 小性的主体对象不同：前者指“图的阶”，后者指“点 数”）•因此，我们质疑WK -证明的做法产生了如 下的逻辑二难困境：若按“临界5图”处理，则其存 在性当今图论无法保证；若按最小图对待，则疑似遭 遇传统的Heawood图的反例攻击.事实上，不同于最 小度5 = 4的安全情形，WK -证明对于有逻辑失误 风险的5 = 5情形反而欠缺完整细节.倡议4：在探索 世界级数学难题时，应防止某些学者打着“不妨假设；同理可证；可以证明”的旗号实施“我断言，你验 证——信不信由你”的行文策略；正因为是世界级数 学难题，一般读者不能直接验证或间接补充.故无论 证明或算法的复杂度多高，严谨负责的做法是提供完 整的对应附件（若长）.我们认为，这是人类挑战机器 证明必须付出的智慧代价.巧合的是，WK-证明全程 使用了 4次“应该是”（should be)•对此我们再次倡 议：针对数学猜想的正式证明不能抱持“猜”的态度或 方法.
第四点,WK-证明采取“反证法中的反证法”的思路本身是合理合法的，但即使把原文中的anyone (任何一人）改为any one (任何一个），后面的推理 仍然违背了逻辑否定的De Morgan律（全称量词V 与存在量词3的互换）.WK-证明在图2中用反证 法证明断言“（所有的）边¥2, ¥3，都在C 中存在”；该命题的否定应为“存在某一条边（基于在 图1中这4条边关于G的最小度顶点w具有（在同构 意义下的）中心对称性，故不妨设），满足隹£( C) •”这是一种常见、可救但必改的逻辑bug.
4结语与展望
(1)我们的反例表明：WK-
证明中使用的新定
第6期杨军，等：简评四定理的一种非计算机“逻辑证明329
义4有缺陷，应首先回归到标准定义4.
(2) 最近一项研究成果[1]业已揭示Kempe不能 证明4CC的根本原因：Kempe变换不能从一个4 -着
导出所有的4 -着.我们的对比分析结果表明：
把Kempe“证明”中的核心概念“最小图”改为“临界5
图”的做法产生了如下的逻辑二难困境：若按“临界
5图”处理，则当今图论无法保证其存在性；若按最
小图对侍，则原文尚缺论证能够抵抗传统的Heawood
图的反例攻击.
(3) 展望：视围棋比赛为一系列2顶点动态演 化（单点增加与多点删除运算）的图变，从近年“围棋
人机大战”（指人工智能围棋程序AlphaG。成功挑战
两名世界顶级围棋大师李世石及柯洁）得到启示：在
大数据、网络通信与人工智能融合发展的新时代，除
非为了锻炼“思维的体操”，追求纯粹数学难题的解决
方案不宜囿于裸脑思维与手工操作的原始心态与自
娱方式，而应与时俱进地接纳/采取基于计算机算法
的辅助证明模式，如文献[15 ].采用手工检查计算过
程的专家们逐步积累并已达成共识[5]：在数学证明中
犯错误的概率远远大于在算法正确性得到证明的情
形下计算机犯错误的概率.故我们预测，在已经拥有
旋转式清堵机
4CC人机合力证明的客观实情下，主观探索4CC的纯
人工证明工作或将被倒逼成为一个“品质更高（包涵
正确性、可读性、简洁性和数学美）的买方（喻指读者
汇流板）市场最后期望，一方面关注近年4CC纯数学证
明的若干新视角、新途径，如与4CC密切相关的整数
流和子图覆盖[~7]、在极大平面图理论架构下从图计
数的角度[1’4]来寻求证明4CC.另一方面，超越趣味
数学游戏精神的初心，寻求现实世界里有广度和深度
的衍生实用，任重道远.参考文献
[1]许进.极大平面图理论（上册：结构-构造-着）[M].北京：
科学出版社，2019.
[2]徐俊明.图论及其应用[M].4版.合肥：中国科学技术大学出版
社，2019.
[3]王献芬，胡作玄.四定理的三代证明[J].自然辩证法通汛，
2010, 32(1) ：42 -48.
[4]许进，李泽鹏，朱恩强.极大平面图理论研究进展[J].计算机学
报，2015, 38(8) : 1680 -1704.
[5]W E S T D B•图论导引[M].2版•李建中，骆吉洲，译.北京：机械
工业出版社，2020.
[6] WANG Y. A Logical Proof of the Four Color Problem[ J].Journal of
Applied Mathematics and Physics, 2020, 8：831 -837.
[7]B0NDY J A, MURTY U S R. Graph T heory[M]. Graduate Texts in
Mathematics, 244. New York：Springer - Verlag, 2008.
[8]D IE S T E L R.图论[M].5版.于青林译.北京：科学出版社，2020.
[9]B0LL0BASB. Modem Graph T h e o ry[M].北京：科学出版社，2001.
[10] BALAKRISHNAN R, RANGANATHAN K. A Textbook of Graph
T h e o ry[M].北京：科学出版社,2011.
[11 ] GODSIL C, ROYLE G. Algebraic graph theory[ M]. Graduate Texts
in Mathematics, 207. New York：Springer - Verlag, 2001.
[12]高随祥.图论与网络流理论[M].北京：高等教育出版社，2009.
[13] WILSON R J. Introductionto Graph Theory ( Fifth Edition) [ M].北
京：世界图书出版公司，2015.
[14] BIGGS N. Algebraic Graph Theory (Second Edition) [M].Cam
bridge University Ptress & Beijing World Publishing Corporation,
2014.
[15] KARD0§ F. A Computer -Assisted Proof of the Barnette -Goodey
Conjecture：Not Only Fullerene Graphs Are Hamiltonian[ J]. SIAM
Journal on Discrete Mathematics, 2020, 34(1)：62 -100.仿真恐龙制作
[16]胡黎莉.符号图的整数流及染问题研究[D].武汉：华中师范
大学，2017.
[17]范更华.整数流与子图覆盖.[J]中国科学（数学），2017, 47
(4)：457 -466.
(责任编辑：付强，张阳，李建忠，罗敏；英文编辑：周序林）
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议