更新时间：2024-09-20 16:06
四色定理（Four color theorem）又叫四色问题或四色猜想，是世界近代三大数学难题之一，其是指每个平面地图都可以只用4种颜色来染色，而且没有两个邻接的区域颜色相同。同时，在图论语言中，也有对四色定理的陈述。
四色问题是英国数学家格色里（Guthrie）在1850年提出的。他的老师德摩根（De Morgan）给出了这个问题的原始表述。随后，很多数学家对该问题展开讨论，肯普在美国数学杂志中的证明引发了数学界的轰动，但后来，有人举出了反例，他的证明并未成功。直到1976年，肯尼思·阿佩尔（Kenneth Appel）和沃卡冈·哈肯（Wolfgang Haken）在肯普证明的基础上借助计算机证明了四色定理。
四色定理为利用计算机进行证明的数学定理，为数学的研究开辟了新的途径。在定理研究过程中，有不少新理论、新思想诞生。此外，在实际生活中、地图着色问题、日程表编排问题、印刷电路板分层问题也和四色定理密切相关。
四色定理的通俗的说法是，每个平面地图都可以只用4种颜色来染色，而且没有两个邻接的区域颜色相同。
平面中面的染色（face-k-coloring），是指种颜色对中面的一种分配，使得公共边的两个面颜色不同。换言之，中面的k染色是映射使得对每个 ，中任何两个面无公共边，记。若平图中的面存在k染色，则称中面色可染（face-k-colorable）。参数被称为的面色数（face chromatic number）。例如。
四色问题即为：为对任何平图，是否有。
1850年，英国数学家格色里（Guthrie）（在伦敦学法律）注意到大多数地图使用4种颜色即可上色，但不知道是否对所有的地图都正确。他就把这个问题提给了他的老师德摩根（De Morgan）。德摩根对这个问题也不能给出答案，1852年，他把该问题以书信的形式提给了汉密尔顿（Hamilton），但汉密尔顿回答说没有时间考虑这个问题。似乎这个问题没有引起他的注意。
1860年， 帕斯（Piece）试图证明该猜想，但是失败了。1878年， 凯利（Cayley）听到这个问题，他在1879发表了题为《关于地图的着色》（《On the coloring of maps》）的文章，在文章中，他解释了该问题证明的难处。
1879年，肯普（Kempe）投了一篇有关四色猜想的文章给美国数学杂志，给出了四色猜想的第一个证明。他的证明在数学界引起了轰动，并因此成为皇家科学家并得到授勋。他的方法一直被沿用。1890年，希伍德（Hewod）发现肯普的证明是错误的，可是他指出肯普的方法虽然不能证明地图着色用4种颜色，但可以证明5种颜色就够了(五色定理)。1898年，希伍德证明了地图上每个区域的边数是3的倍数时，四色定理成立。这以后，人们开始考虑通过限制地图的区域来证明四色定理。
1922年，富兰克林（Franklin）证明了最多有25个区域的地图是四面可着色的。1976年，牧野（Muyer）证明了最多有90个区域的地图的四色问题。1976年，美国伊利诺伊州大学的肯尼思·阿佩尔（Kenneth Appel）和沃卡冈·哈肯（Wolfgang Haken）把四色问题归结为2000个不同的组合结构图形，利用三台高速IBM360计算机对这些图形进行分析，用了1200机时，近百亿次逻辑判断，证明了“四色定理”。1977年，证明的细节发表在文章上，争议也从此开始。争议的中心是人们能不能、该不该接受这个证明。1996年，罗伯森（Robertson），桑德尔（Samders），西摩尔（Seymour），托马斯（Thomas）给出另一个机器证明。他们利用了更有效的方法，使用时减到633小时。
肯普用图论的知识对于四色猜想进行了证明，首先需引入如下基础概念。
每个有界面的度都为3的平面被称为构形。如图1所示四个平面都是构形，分别记为。
设是由有限个构形组成的集。若任何三角剖分图至少含中一个构形，则称是不可免完备集。由于任何平面的最小度不超过5，所以是不可免完备集。
一个构形被称为可约的，如果它不含在任何一个最小图中。
若四色猜想不成立，那么必存在一些5色平图，其中阶数最小的被称为最小图。
肯普是通过证明最小图不存在来证明四色猜想的，证明过程如下。
反证：设是最小图，则是三角剖分图。因此，必须含中的构形，若含或，则
。令是中点的4染色，则至多只需三种颜色，矛盾于，所以不含构形和。
设含构形，且，是中的4染色，并不妨设，其中颜色标在该点上，则在中和在中不同时都是连通的，否则，中路和中路会相交，如下图所示：
不妨设和在中不连通。于是，交换中含连通分支中点的颜色，被染上颜色4，而的颜色不变。空出颜色1来染点，即，矛盾于，所以不含。
肯普采用同样的方法证明也不含构形。于是三角剖分图不含中任何一个构形，矛盾于是不可免完备集，从而证明了最小图不存在，即四色猜想得证。
高速数字计算机的发明，促使更多数学家对“四色问题”进行研究。从1936年就开始研究四色猜想的海克，公开宣称四色猜想可用寻找可约图形的不可避免组来证明。他的学生丢雷写了一个计算程序，海克不仅能用这程序产生的数据来证明构形可约，而且描绘可约构形的方法是从改造地图成为数学上称为“对偶”形着手。
自从“可用寻找可约构形不可避免组的方法来证明四色猜想”这一猜想提出后，人们沿着这一思考路线采用各种方法来寻求可约构形的不可避免组。后来，这一猜想的提出者希什（Hish）运用移植手段，将物理学上一种在电网络中国移动通信集团电荷的“放电法”应用到这一问题的探讨之中，即用“放电法”来寻求构形的不可避免组。这种方法虽然很初步，尚待完善，但却为后来证明四色猜想奠定了良好的基础。
20世纪70年代初，美国数学家赫尔曼·哈肯试图以改良了的放电方法来证明四色猜想。但是，他遇到了困难：可约构形的任何一个不可避免组都可能有很大的构形，其计算量十分巨大。后来，他逐步认识到，用人工方法是无法完成这一巨大工作量的。于是，他便开始寻求新手段，从数学之外来选择新工具，并自然联想到具有极大计算能力的高速电子计算机。比如，哈肯于1972年就作出了“肯定不会对四色猜想给出一个非机器证明”的结论。即只有在方法上实行革命性的变革，运用现代技术成果——电子计算机这个有效工具，即采取机器证明的方法，四色猜想才可能获得最后解决。
1972年，阿佩尔与哈肯设计了一个新的计算程序。这个程序不仅能作出特殊类型的放电过程，而且还能给出从最重要的情况得出的构形作为输出。经过实际计算和不断修改得到了一个可行的程序，并通过它证明了地图上可约构形的不可避免组的存在性。后来，他们又经过不断修改程序，反复实验，改进放电过程，并于1976年1月6日通过电子计算机找到了可约构形的不可避免组，从而完成了四色猜想的证明，最终获得了 “四色定理”。
在计算机证明过程中，阿佩尔和哈肯构造了1478个构形，后来罗伯森、桑德尔、西摩尔、托马斯等人将构型减少到633个，但对于人来说，证明633个构型是可约的仍然是一个困难的问题。
例如：设图中每个顶点都是三次的，每个区域图都有偶数条边和偶数个顶点，且每条边上都有一个区域图相邻，则此平面可用三种颜色染色，即
和
证明：肯普的证明方法是利用一个多区域图（子图）的组合构形图来进行文字叙述证明的，如下图
从上图中可以看出，题中所设定的每个顶点上的次数为和每个区域图都有偶数条边及偶数个顶点，且每条边上都有一个区域图相邻的条件成立。在对整个图染色时没有超过三种颜色，同时，又满足了在区域图上相邻的每条边上都染上了一种颜色，由此形成了整个图中每个顶点上都染上了不同的颜色和相邻在每条边上的两个面都染上了不同的颜色。
五色定理：用5种颜色可以给任意简单连通平面图正常着色。
证明：对图的顶点数作归纳。
（1）当时，显然成立。
（2）假设个顶点时成立，下面考虑阶简单连通平面图。
由定理在简单连通平面图中至少有一个顶点，其次数可知，图G至少存在一个顶点，其次数。显然是阶简单连通平面图，由归纳假设可用5种颜色进行着色。
假设已用红、黄、蓝、绿、黑5种颜色对着好了色，现在考虑对中顶点进行着色。
1）若，显然可用它的邻接顶点所着颜色之外的一种颜色对进行着色，即可以用5种颜色着色。
2）若，显然只需考虑与邻接的顶点被着以不同的5种颜色的情况进行讨论。
令，，考虑导致的的导出子图。
a）若和分别属于的不同连通分图，那么将所在分图的红蓝色对调，并不影响图的正常着色。然后将着上红色，即得图的正常着色。
b）若和属于同一分图中，则和之间必有一条顶点属于红蓝集的路径，它加上可构成回路。
由于的存在，将黄绿集分为两个子集，一个在内，另一个在外，于是黄绿集的导出子图至少有两个分图，一个在内，一个在外。于是问题转化为a)的类型，对黄绿集按a)的办法进行处理，即得图的正常着色，证毕。
构造一个具有无限色数的局部有限可数图。
解：只需取是所有的并集，其中是所有正整数。
注：如果希望图是连通的，那么将的一个顶点与的一个顶点相连，的一个顶点与的一个顶点相连，依此类推。
例1：如果一个无限图连通并且局部有限，其所有顶点的度数是偶数，那么它是否必须包含双向无线的欧拉步道（即顶点序列使得是一条边，并且图中的每条边恰好出现一次）。
解：否。取反例为有共同起点的四个不同路径组成的图。
例2：证明在顶点存在一个可数图，其中。
证明：归纳构造这个图，首先连接，于是达到要求，剩余的顶点的度数为0或1。假设已经得到一个图，使得个顶点的度数达到要求，其余顶点的度数为0或1，将连接到所需个数的度数为0的顶点，则，接下来面对的就是个顶点到达要求的情况。最终，任何两个顶点的连接方式确定，得到了所需的可数图。
在任何一张地图上，总能用四种颜色给各个国家着色，使得邻国的颜色不同。这里的地图不包含那种稀奇的故意找别扭的“人造地图”。比方世界是一个圆，从圆的中心作条半径，将圆分成个国家，则个国家均为相邻于圆心的邻国，于是要做到邻国的颜色不同，就要用种颜色了。这里的邻国是有共同边界线（不是有限个点）的连通区域，满足这个条件的区域被称为“构形”，如此形成的地图被称为正规地图。在正规地图中，没有三个以上的区域相交于一点，并且没有一个区域完全包围另一区域。世界上绝大多数的地图都是正规的。
一些日程表编排问题也可以看成四色问题，例如，每逢学期结束，学校总要安排期终考试。尤其在实行学分制的大学里，考试日程表的编排是很有讲究的，既要做到日程安排紧凑有序，又要杜绝某生选修的两门课程同一时间考试的情况出现。设想个学生构成点集，门课构成点集，学生选课程，则在之间以线相连，这样便组成一个偶图。给中的边染上各种颜色，颜色相同的边所对应的课程在同一时间考试。接下来考虑的问题就是选用尽可能少的颜色，使得从中同一点出发的边具有不同的颜色。此外，四色问题在有效地设计航空班机日程表方面也起到了推动作用。
印刷电路板的分层问题也是四色问题的应用。将四色图的边对应于导线，顶点对应于接点，没有导线连接的两个接点间可能要装配元件。