四色问题与五色定理

1、四色问题与五色定理摘要：1852年一位伦敦的大学生替他的哥哥向数学家De Morgan提出了一个问题：任何一张地图是否仅需要四种颜色即可将所国家着色，并且所有相邻的国家具不同的颜色？这就是著名的四色问题或四色猜想。时隔一百多年后的1976年，美国伊利诺斯大学的两位教授Appel和Haken利用计算机肯定了四色猜想的正确性，但是数学家寻求“人工”证明至今未果，这真是对人类智慧的考验。本报告将用十分钟的时间介绍四色问题的历史和图论方面的一些基本知识，以及五色定理的证明过程。希望大家在讨论班上度过一个愉快的周五下午。 本报告的内容主要根据文献1编写。 1. 四色问题的历史1852年10月23日英国数

2、学家Augustus de Morgan写信给三一学院的友人数学家William Rowan Hamilton，信中写道： “我的一个学生今天要我为他提供一个充分的理由，来说明一件我自己还无法判明究竟是对还是错的事实。他说，如果画一张图，图上任意分成许多部分，凡是有共同边界线的两个部分都要涂上不同的颜色，那么，大概需要四种颜色，而不需要更多的颜色就可以了。请问：难道不能够构造出一个需要五种或者更多种颜色的图吗？” 这就是所谓的四色问题，可惜Hamilton并没有重视这个问题。 二十六年之后，在1878年6月13日的伦敦数学会上，数学家Cayley正式提出了四色问题。这个问题引起了很多人的兴趣，

3、包括很多业余爱好者，其中有师律出身的Kempe和法国文学教授Mayer等。Kempe曾声称自己已经解决四色问题。后来不久，就被当时才二十多岁的Heawood指出其证明中的漏洞。Heawood一生研究四色问题共六十年，发表过几篇重要的论文，虽然没有最后解决四色问题，却证明了五色定理(1890)，又称Heawood定理。1913年美国数学家伯克霍夫发现一些新的可约构形。 1968年挪威数学家奥雷等人证明了用四种颜色一定可以把不超过四十个国家的地图着色，推进了四色问题的研究。70年代初人们努力寻找可约构形中的不可免完备集，因为用它可以通过数学归纳法证明四色问题。 1976年美国伊利诺斯大学的两位教授

4、Appel和Haken采用Kampe在1879建立的一种思想，利用计算机肯定了四色猜想的正确性。Appel和Haken花了1200多小时的电子计算器工作时间，找到一个由1936个可约构形所组成的不可免完备集，因而在美国数学会通报上宣称证明了四色猜想。后来他们又将组成不可免完备集的可约构形减至1834个。四色问题的研究对平面图理论、代数拓扑、有限射影几何和计算器编码程序设计等理论的发展起了推动作用。2. 平面图与欧拉公式一个图是由一些点和线构成，这些点称为顶点，线称为边，如图1。 图1 平面图如果一个图能画在平面上，而各边不相交，这样的图称为平面图，否则称为非平面图。图1(a)是平面图，实际上，

5、图1(b)也是平面图，因为它们是同构的。任何一个凸多面体都可以用一个平面图来表示，如图2(a)是正六面体和其在平面上表示，图2(b) 是正十二面体和其在平面上表示。 图2 (a) 正六面体 ；(b)正十二面体对凸多面体有著名的欧拉公式 (1)其中、分别是凸多面体的顶点数、边数和面数。例如，对正六面体：、；正十二面体：、 ，(1)式都是成立的。 如果一个图，对图的任何两个顶点都有由边构成的路将它们连接(关联)，此图称为连通的，否则称为不连通的。如图1和2中的图都是连通的，而图3是不连通的。显然一个不连通图是由若干个连通分支组成，如图3中的图有两个连通分支。 图3不连通图定理1 对任何一个连通的平

6、面图，欧拉公式 (2)成立。证：对边数用数学归纳法。当时，连通图有一个顶点和一面，即和，故(2)式成立。设对任意具有条边的平面连通图，(2)式成立。一个具有条边的平面连通图可由一个具有条边的平面连通图(图4(a)添加一条边而形成，如图4(b),(c)所示。由归纳假设，对图4(a)，(2)式成立。对图4(b)中的增加边方式，图的顶点数未变，而边数和面数与图4(a)相比，各增加1，(2)式仍然成立；对图4(c) 中的增加边的方式，图的面数未变，而顶点数和边数各增加1，(2)式仍然成立。由归纳法，(2)式对任意的平面连通图成立。 图4 (a)条边的平面连通图；(b)和(c) 条边的平面连通图现在来谈

7、地图着色问题了。地图着色问题中，我们假定任何一个国家是由一个单连通的区域组成，任意两个相邻国家之间的边界只有一条。如图5(a)中区域代表了五个国家，我们将每一个国家用一个顶点表示，图5(b)中顶点分别代表了国家 图5 地图着色的图表示 。如果两个国家相邻，就用一条边将代表这两个国家的顶点连接起来，这样就得到一个平面图5(c)。由前面的假定，由地图导出的平面图满足两个条件：(1)任何两个顶点之间至多有一条边；(2)而图中没有连接同一个顶点的边（即“环”）。假定以下提及的平面图都是满足这两个条件的，不再重复说明。 四色问题就可表述成：对任何一个平面图，总可以用四种不同颜色将图中所有顶点着色，使任何

8、相邻顶点具有不同的颜色(两个顶点相邻指它们之间有一条边)。 以下我们将给出关于平面图的两个引理，在此基础上，再给出五色问题的证明。引理1对任一个连通的平面图，必然有 (3)证：图中任一个面至少由三条边围成，而一条边至多是两个面的边界，故有 或 (4)由欧拉公式(2)，得 或 显然(3)式对不连通的平面图也成立的。例1 试证明图6(a)和(b)中的图是非平面图。 图 6 非平面图证：(a) 对图而言，(3)式不成立，故是非平面图。 (b) 对图而言， ，(3)式成立，但无法用其判定是是平面图还是非平面图。反设是平面图，的每个面至少含4条边，而每条边至多在2个面中出现，故有或，由欧拉公式(2) 或

9、 (5)但与(5)矛盾，故是非平面图。引理2对任一个平面图，必然有一个顶点其上关联边的数目小于或等于5。证：如果每顶点其上关联边的数目大于或等于6，那么就有 (6)此与(3)式是矛盾的，引理结论正确。3.五色定理的证明定理2(Heawood定理) 对任何一个平面图，总可以用5种不同颜色将图中所有顶点着色，使任何相邻的顶点具有不同的颜色。证：对图的顶点数进行数学归纳法。当时，定理显然成立。设定理对任意具有个顶点的平面图成立，设现考虑具有个顶点的平面图。由引理2，中必然存在一个顶点，其度数(即关联的边数)，在图去掉顶点和与它相关联的边，得到一个具有个顶点的平面图。由归纳假设，可将的所有顶点用5种不

10、同颜色着色。如果，或但是与其关联的5个顶点只着有4种不同颜色(图7中数字分别表示不同颜色)，如图7(a)，那么定理结论成立。余下的要考虑是，与顶点关联的5个顶点用了5种不同颜色的情况，如图7(b)所示。对这种情况，顶点和顶点是相互分隔开的。选定顶点，在图中只保留着色为和的顶点及它 图7 度为5的顶点 图8 图 们之间的边，去掉其它的顶点和边，得到图，然后分两种情况：(i) 顶点和不属于图的同一个连通分支，如图8(a)；(ii) 顶点和属于图的同一个连通分支，如图8(b)。对情况(i)，将图中含顶点的最大连通分支中各顶点的颜色互换(颜色1和颜色3互换)，然后将顶点着颜色3；对情况(ii)，在图中就有一个回路，顶点、和在此回路上，除顶点外，此回路其它顶点的颜色是1或是3，并且是相互间隔的。顶点和中有一个在此回路中，不妨设顶点在此回路内部。只保留着色为2和4的顶点及它们之间的边，去掉其它的顶点和边，由图得到图，图中含顶点的