图说四色问题 目录

**章 历史的回顾
1.1 问题的提出
1.2 简与难的巧妙结合——四色问题迷人之处
1.3 两个有漏洞的伟大证明
1.4 关于四色问题的几则逸事
1.5 平凡而又深藏陷阱——四色问题又一迷人之处
1.6 艰难的进展
1.7 怪事：“复杂反简单，简单反复杂”
1.8 加德纳的玩笑
1.9 关于四色定理的计算机证明
1.10 近30年来状况
1.11 关于“*迷人数学难题”的网络评选
第二章 初等图论和四色问题的数学描述
2.1 描述地图着色的几种形式
2.2 数学中的图(graph)
2.3 平面图和非平面图
2.4 欧拉公式
2.5 四色问题特圳关注边*多的图
2.6 着二色的奇偶层法
2.7 极大平面图分解为层圈结构
2.8 二重奇偶层分解
2.9 幻想的分解、实例和理性认识
2.10 四着色的直观和数字化表示
2.11 用符号表示未得到的四着色
2.12 极大平面图和平面三次图
2.13 字母符号使用说明
第三章 叫着色算法和例图的**轮计算
3.1 算法A的举例说明
3.2 算法A的思路和主要步骤
3.3 Maple帮助我们快速、高效地编程
3.4 **批例图的选择确定
3.5 **批例图的**轮计算
3.6 四着色的图形展示、观察
3.7 美哉、妙哉——图形观察后的感言
第四章全部四着色和四着色不变量
4.1 Kempe二色变换和四着色树
4.2 四着色树的计算和观察
4.3 展示全局结构的四着色树
4.4 四着色不变量
4.5 四着色不变量的图说和汪明
4.6 梳理綮多、杂乱为统一、有序的四着色不变量
4.7 关于色多项式计算
4.8 求全部四着色的算法
4.9 **批例网全部四着色计算结果
4.10 三个著名例图全部四着色的统计
4.11 四着色实例中的高次点
第五章 四着色类型和哈密顿性
5.1 极大平面图和平面三次图
5.2 哈密顿圈与树-树型四着色
5.3 二元哈密顿圈与树-圈-树型四着色
5.4 多元哈密顿圈与四着色的支系参数(Cr，Cs)
5.5 泰特猜想的修正
5.6 把看似无关的慨念联系起来
第六章 由计算得到的定理及逻辑证明
6.1 当已经获得全部四着色时
6.2 由计算得到的定理
6.3 人工逻辑证明和计算机证明
6.4 等待你去探究的无尽奥秘
参考文献
后记

图说四色问题 本书特色

本书尽管篇幅不大，但内容独具特色。它基本上没有罗列四色问题的
各种等价命题，对四色定理机器证明仅有数百字介绍，而主要是对一些简
单例图及四色问题历史上著名例图，给出较为丰富的、直观的、具体四着
色结果，包括大量图形、表格。二十来个例图具体四着色的各种图、表和
对这些图、表的解说构成本书主体。这种安排显著降低了阅读难度，对多
数读者来说，更加通俗、直观、生动。
——中国科学院院士张景中
如果说四色问题的魅力曾经引诱众多知名数学家为之倾心，那么，许
寿椿的这本《(图说四色问题)》对广大非专业的数学爱好者来说，也许有更
多的魅力。它不仅仅把那些知名数学家在四色问题面前跌倒的故事娓娓道
来，而且着手研究用合理的算法来实际实现对任何图的四着色，进而对历
史上若干难于四着色的著名例图的确给出了四着色。它于是启发我们：如
果你能够提出一种算法，并且又能证明这种算法对任何有限图总能成功地
实现四着色，那你就把“四色问题”变成了“四色定理”了，这也许是本
书更为诱人之处!
——北京大学教授武际可

图说四色问题 节选

兴地阅读了《图说四色问题》的书稿，认为该书稿是一部具有原创性的科普佳
作，适合中学生、大学生、研究生，数学教师和数学爱好者阅读。写下面的几段话向读者
推介。
四色问题是一个世界著名数学难题。对它感兴趣甚至迷恋它的大有人在。在各种教
材与专著里以及数学普及读物里，往往都会讲到它。遗憾的是，一般除简单历史介绍外，
大多注重四色定理的各种等价命题的解说，以及四色定理机器证明方法的讲解，更具体
实在的就很少涉及了。本书尽管篇幅不大，但内容独具特色。它基本上没有罗列四色定
理的各种等价命题，对四色定理机器证明仅有数百字介绍，而主要是对一些简单例图及
四色问题历史上著名例图，给出较为丰富的、直观的、具体四着色结果，包括大量图形、
表格。二十来个例图具体四着色的各种图、表和对这些图、表的解说构成本书主体。这种
安排显著降低了阅读难度，对多数读者来说，更加通俗、直观、生动。
在长达一个半世纪的进程中，有众多知名数学家投身于四色问题。四色问题现今有
数十种变体、等价说法和各种推广。但四色猜想本身的研究却进展缓慢。直到1976年美
国数学家给出四色定理的计算机证明，其基本证明思路“可约构形不可避免集合”的检
验．仍然不容易用简单通俗的语言说得十分清楚明白。再者，由于传统的用纸、笔研究数
学方法的局限，使十来个点的图(十来个国家的地图)的完整四着色分析，用手工的办法
难于进行，、一百多年来大量论文和四五十年来的不少专著、教材里，难于看到着了四种
颜色的非平凡例图。这反映出人们对四色问题的认识还很初步，对具体图的四着色属性
还知之甚少。这些使得四色问题的普及带有源于自身的固有困难。本书的新意，不完全
是由于作者叙述、表达方面的写作技巧，而是由于作者在十多年潜心研究中处理了大批
例图，获得丰富的、**手原始基础资料。这些资料容易用图形、表格方式表达。这使得
四色问题开始变得直观、形象、具体。容易发现，作者对资料认真地做了加工。对不少例
图做了十分认真、细致的设计。作者利用其研究所得**手资料，把四色难题的种种概
念做了深入浅出、直观具体的表述，使得抽象、繁难的问题向简单、通俗跨了一大步。
本书中的素材主要来自作者自己的研究。作者处理的例图较为系统、完整(包括各
已知著名例图和*小的四连通极大平面图、五连通极大平面图)，例图的加工、处理较为
细致、深入，所得**手资料较为丰富。这些素材是其他专著及普及读物里现在还见不
到的。因而本书有突出的原创性特点。
对于一般数学的求解问题，特别是组合数学的求解问题，通常要顺次地研讨：问题
有没有解：解是唯一的还是批量的；唯一性证明或全部解的数量和结构性质；与批量解
结构相关的不变量：解的性质与该问题其他相关属性的关联等等。四色问题长期以来，
主要还在研讨有没有解的问题。至于有怎样的解，解的属性和结构，四着色和其他属性
的关联，还都极少涉及。本书中，作者精选了自己十多年研究的部分结果，做了通俗化介
绍。这里包括：求出部分解：由单个解求出可由它经过二色变换得到的众多解(由根四着
色生成四着色树)：算出一个图的全部四着色总数并具体算出全部四着色解；四着色不
变量的发现和论证：四着色类型与哈密顿性关系等等：相当直观地、通俗地讲述了这些
较为系统的新结果。许多图表作为四色问题的基础材料，对读者增加知识也有很大帮
助。也是许多读者，特别是数学爱好者都感兴趣的。
作者联系着四色问题的历史，依据自己研究工作的进程，细致、具体地描述了四色
问题的种种迷人之处和一些重要进展的由来。作者恰当地采用功能强大的电脑和数学
软件为工具，认真地、脚踏实地地进行原始资料(集中于批量例图的具体四着色)的发
掘、搜集。具体展示了这个过程概貌并努力引导读者一起观察、分析、探索，共享发现的
乐趣。书里逻辑证明很少，并都十分初等、简单。主要是基于平面图欧拉公式的多元一次
式的简单变换。简单、初等的方法能导出一些有价值的新结果，作者自认为是电脑和软
件的作用。作者把这和伽利略用望远镜发现月球上的环型山相比较，用以说明：合理的
科学方法、研究工具和老实的科学态度*为重要。
现今在广大数学爱好者中，有些人偏于急躁求成，不安心于踏实、细致的工作，盲
目、轻率地发动对数学难题的攻坚。有些人稍有所获，就宣称自己有了重大发现、重大贡
献，甚至轻率否定学界公认的已有结果。比较起来，本书作者十多年里脚踏实地，默默无
闻．耐心、细致地“做例子”，积累基本事实资料；在对丰富资料的观察中力争有所发现，
有所前进。这对爱好科学的读者们，会有积极的影响和启发。
代前言
致青少年朋友和他们的老师
这是写给广大科学爱好者，特别是青少年读者的一本普及读物。本书主要用图、表
及其解说来介绍著名的四色问题。所用图件主要有两类：几位重要数学家的照片，和用
来展示例图着色属性的图件，这一类占绝大部分。后者是作者用Maple软件(主要是其
中的图论程序包)处理大量例图时得到的(但本书不涉及Maple的具体使用，对它毫无
了解不影响阅读)。由于十来个点的平面图着色问题单用手工已经难于处理，所以150
多年来大量关于四色问题的论文和专著中，很难看到着了四色的非平凡例图。至
今人们对具体图的四着色属性还知之甚少。应当说“四色公主”还是“藏在深闺人未识的
大家闺秀”。本书结合二十来个例图给出的资料应陔算是较为丰富、较为生动、较为有趣
的。这些使得我们的“四色公主”变得多彩、美丽、迷人。本书作者愿意与广大青少年朋友
共享这种乐趣。书中所选用的例图，包括学界熟知的四色问题著名例图(如：希伍德反
例图、塔特反例及其同类图4个、加德纳难四着色图等)，一些*小例图(*小四连通6
个．*小五连通3个)及几个另外的例图。对于大多数例图(包括希伍德反例图、塔特反
例图)，我们都得到了其全部四着色。*小的8个图的全部四着色都用列表形式给出(其
他的因数据量太大而从略)，图示了它们的种种着色属性。在我们观察、分析具体例图大
量**手资料时，也发现、论证了一些规律性的东西，如全部四着色的森林结构、四着色
不变量等等，并都做r图示和说明。
本书中逻辑推理的内容极少，基本是基于平面图欧拉公式多元一次式的简单演算，
初中生都会做。书中的全部叙述都是初等的。用完全初等方法能获得有价值的新结果
吗?不必怀疑。想当初，伽利略发现月球上的环行山，主要不是因为伽利略的“绝顶聪明
的头脑’’和“十分神奇的双眼”，关键是他改进了望远镜并把它对准了月亮(这才是关键
的)。成就**位细胞生物学家的，也不是他的“绝顶聪明的头脑”和“十分神奇的双眼”，
关键是种种主客观条件使他把切片放到r显微镜下。我相信，当伽利略把望远镜交给你
时，只要你也把它对准月亮，认真地看一下，你一定也会有所发现。
2005年在国内成功完成了一次“世界*迷人数学难题”的网络评选(其简要情况介
绍见本书】．11古)。四色问题以63 987票当选第二名。有评沦家认为，这次评选有36
万爱好者参加(经过严格审查确认有效投票202 432张)，并且成功完成，足表明我国公
众科技素养有提高的可喜事件。作者认为，这得力于近许多年来众多科学家、教育家的
不断的、有效的呼吁，与有关部门切实的如下工作有关：要十分注意保护、培养青年的
科学兴趣；要十分注意保护、培养青年的对科学的好奇心、求知欲；要十分注意保护、培
养青年对科学的探索欲、创造欲；要批评那些完全功利又近于残酷的强化集训1、题海大
战，尽管这些对增加知识、提高技能有短期效果，但对学生自主创造能力的培养和身心
健康可能造成更严重危害。作者为有36万爱好者的参加感到欣喜。是的，兴趣足*好的
老师，强烈的好奇心、探索欲是创造发明的必要条件。看到有这许多数学爱好者，是激励
作者抓紧写出这本书的动因之一。本书的绝大部分，都是对四色问题采川初等图论方式
所做的通俗但也是细致认真地讲解：书中也用少量篇幅写小r作者学习、探索过程十的
观察、思考、心得，和对四色问题的奥妙、美妙、迷人之处的若干评说。这样的安排是希望
对读者增加对数学科学的兴趣、好奇心有所帮助，对激发读者的求知欲、探索欲有所帮
助。本书内容的安排，大体依照作者自己学习、探索的经历。这样做，可能容易说清自己
的思路，容易和读者进行交流。如果本书的某些图、表、论说在读者心理留下一些记忆，
或者引发了、增加了他们的兴趣，或者引发了、增加了他们的探索欲望，作者将由衷感到
欣慰。
书中列出少量必要的文献，它们对想进一步学习的读者和辅导教师可能有用。
本书**次稍许完整地介绍了作者关于四色问题计算机辅助的研究。限于篇幅，
限于图说表达方式的局限，不少内容没有包括，许多内容被删节了。作者很希望有机会
把相关工作向读者做更完整、更细致地介绍，与朋友们共享学习、实验、观察、探索、
发现的快乐，共同欣赏四色难题。渎者有什么意见、建议、希望，可以直接通过作者的博
客进行交流。

图说四色问题 作者简介

作者简介
许寿椿 中央民族大学教授。1963年毕业于北京大学数学力学
系并留校任教。1985年调入中央民族学院任教，从事计算机软件、离
散数学、中文信息处理等教学和研究]二作。曾获国家科技进步三等
奖、国家民族事务委员会科技进步一等奖。发表论文80余篇，著作11
种．其中畅销书类著作有：《