四色定理 (2-1)

一个很有名的例子是这个对四色定理的简短的证明(Alfred Kempe, 1879)，直到11年后才有人(Percy Heawood, 1890)指出了这个证明的错误。

这个证明需要用到一个引理，由于证明并不是很复杂（用欧拉公式）而且不是本答案重点（ie 它的证明是对的），我们就不证它了：

引理 一个n＞=3个顶点的平面图G最多有3n-6条边。

现在我们来证明四色定理。

定理 对任何平面图G，都可以给G的每个顶点分配一个颜色，使得任何G中的边的两个顶点颜色都不同。

这个定理的描述和通俗版本的不太一样：四色定理的通俗版本是说，任何一个平面上的地图都能用四种颜色染色使得相邻国家的颜色不同。我们可以想象每个国家有一个首都(G的顶点)，每两个相邻国家的首都之间都有一条不一定是直线的路(G中的边)。于是通俗版本的四色定理就变成了上面的图论描述。

证明：

设G是一个n个顶点的平面图。n＜=4的情况显然正确。现在对n进行数学归纳法：当n＞4时，取一个G的度（相邻顶点的数量）最小的顶点v，由之前的引理我们知道v的度最多是5。根据归纳法假设，图G-v(ie将v移除后的图)是可以用四种颜色染色的。现在将G-v用四种颜色染色，然后考虑与v相邻的点。如果它们没有用到全部4种颜色那么我们就可以用剩下的颜色染v了。不然，在平面上画出G（取一个G的drawing），然后分类讨论：

(1)v的度是4。设和v相邻的顶点按顺时针顺序为a,b,c,d，不妨设它们的颜色按顺序分别为1-4。现在补充一个定义：称一条G-v中的路径为(i,j)-路径，如果路径上的顶点的颜色按顺序依次间隔为i和j。现在考虑由a出发的所有(1,3)-路径。如果c不在任何这样一条路径上，那么我们直接把所有这样的路径上的1和3交换即可让a用3染色同时不破坏剩下的图G-v的四色染色。然后用1来染v即可。不然，我们有一条从a到c的(1,3)-路径。由于G是平面图而且abcd是按顺时针排列的(见下图)，我们知道不可能存在从b到d的(2,4)-路径了，于是把从b出发的(2,4)-路径上的2和4交换即可；

(2)v的度是5，和v相邻的顶点按顺时针顺序为a,b,c,d,e，且颜色按顺序为1,2,3,4,1(只是一种情况)。考虑从b开始的(2,4)-路径，如果d不在任何一条这样的路径上那么和第一种情况类似交换b开始的(2,4)-路径上的2和4即可；不然如果b到d有一条(2,4)-路径，从c到a和e就无法有(1,3)-路径了(见下图)，不然G不是平面图。于是和第一种情况类似可以解决这种情况；

(3)v的度是5，和v相邻的顶点按顺时针顺序为a,b,c,d,e，且颜色按顺序为1,2,3,1,4。注意到实质上不同的染色只有这种情况和上面的第二种。现在如果e不在b开始的(2,4)-路径上，或者e不在c开始的(3,4)-路径上，我们都可以交换b或c开始的对应路径上的颜色从而解决；不然，e有一条到b的(2,4)-路径，而且有一条到c的(3,4)-路径。但是这样一来，a到c就无法有(1,3)-路径，而且d到b也无法有(1,2)-路径了(见下图)，于是我们交换a的(1,3)-路径上的1和3，以及d的(1,2)-路径上的1和2，于是a变成了颜色3，d变成了颜色2。现在我们就可以把v用1染色了。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。