任何地圈上的国家只需用4种颜色来染，使得任何具有共同边界的两个国家颜色都不相同。 ----这就是著名的四色猜想！ 著名的四色问题最早见于1852年10月25日伦敦数学家摩根(De Morgan)致 爱尔兰数学家的哈密尔顿(W.R.Hami Iton)爵士的一封信中，信中说“我的一个学 生今天要求我说明一个事实的理由，我不知道这事实是否确实的，所以未予回答.他 说，如果一个地图被任意划分，并把各部分染上不同的颜色，使得具有公共边界 线的各部分都有不同的颜色，这样四色足够而不必更多”。这个学生就是弗吉德 里克·葛斯里(Francis Guthrie,后来是一个物理学家)，他说他这个问题来自他 的哥哥弗兰西斯·葛斯里(Frederick Guthric,他后来是一个数学家)，而他提出 的这个猜测是与英国地图的染色有关的. 1879年.Kempe发文声明给出了这个猜想的第一个“证明”，可是1890年P.J. Heawood给出了一个反例说明Kempe的证明存在严重的漏洞，而且Heawood利用Kempe 的思路证明了：每个平面图是5-可染的。为了大家更好地理解此问题，我们用图论 的术语来叙述此问题。先给出一些概念
任何地圈上的国家只需用4 种颜色来染，使得任何具有共同边界的两个国家颜色都不相同。 ------这就是著名的四色猜想！ 著名的四色问题最早见于1852 年10 月25 日伦敦数学家摩根(De Morgan)致 爱尔兰数学家的哈密尔顿(W. R. Hamilton)爵士的一封信中，信中说“我的一个学 生今天要求我说明一个事实的理由，我不知道这事实是否确实的，所以未予回答.他 说，如果一个地图被任意划分，并把各部分染上不同的颜色，使得具有公共边界 线的各部分都有不同的颜色，这样四色足够而不必更多”。这个学生就是弗吉德 里克·葛斯里(Francis Guthrie，后来是一个物理学家) ，他说他这个问题来自他 的哥哥弗兰西斯·葛斯里(Frederick Guthric, 他后来是一个数学家) ，而他提出 的这个猜测是与英国地图的染色有关的. 1879 年.Kempe发文声明给出了这个猜想的第一个“证明”，可是1890年P. J. Heawood给出了一个反例说明Kempe的证明存在严重的漏洞，而且Heawood利用Kempe 的思路证明了：每个平面图是5-可染的。为了大家更好地理解此问题，我们用图论 的术语来叙述此问题。先给出一些概念
1.平面图：如果把一个图画在平面上时，能够使它的边仅在端点处相交，那么称 这个图为平面图 有些图形从表面上看有几条边是相交的，但是不能就此肯定它不是平面图，例 如图(1)，表面看有几条边相交，但是把它画成与它同构的图(2)，则可看出它是一 个平面图 但是有些图无论你怎么画，它都不可能是平面图，如下两图（第1个图是两边 都是3个点的完全二分图，第2个图是5个点的完全图)：
1.平面图：如果把一个图画在平面上时，能够使它的边仅在端点处相交，那么称 这个图为平面图. 有些图形从表面上看有几条边是相交的，但是不能就此肯定它不是平面图，例 如图(1)，表面看有几条边相交，但是把它画成与它同构的图(2) ，则可看出它是一 个平面图. 但是有些图无论你怎么画，它都不可能是平面图，如下两图（第1个图是两边 都是3个点的完全二分图，第2个图是5个点的完全图）：
2.面：一个平面图G把平面划分成若千个连通区域；这些闭区域称为G的面.每 个平面图恰有一个无界的面，称为外部面。前面讲到的四色问题就是：对任何一个 平面图，都可以用四种颜色对它的面进行染色，使得相邻的两个面之间用不同的颜 色。 3.对偶图：给出平面图G,可以定义另一个图H如下：对于G的每个面f,都有H的 一个顶点与之对应，对于G的每条边e,都有H的一条边e*与之对应；H中两点u和v由 边e*相邻当且仅当G中与顶点u和v对应的面f和g被边e分隔，则称图H称为G的对偶图. 容易看出，平面图G的对偶图是平面图，平面图的对偶的对偶就是它自己.对偶图 就是把原来平面图的面变成了它的对偶图的点，两个面相邻对应的就是两个点相邻， 平面图的面染色就变成了它的对偶图的，点染色。所以四色问题又可以改成：对任何 一个平面图，都可以用四种颜色对它的点进行染色，使得相邻的两个点之间用不同 的颜色。由于点与点之间的相邻要比面与面之间相邻要更容易辨别，所以下面我们 说的四色问题就是说平面图的点染色
2.面：一个平面图G 把平面划分成若干个连通区域;这些闭区域称为G 的面. 每 个平面图恰有一个无界的面，称为外部面。前面讲到的四色问题就是：对任何一个 平面图，都可以用四种颜色对它的面进行染色，使得相邻的两个面之间用不同的颜 色。 3.对偶图：给出平面图G ，可以定义另一个图H如下:对于G 的每个面f，都有H 的 一个顶点与之对应，对于G的每条边e，都有H 的一条边e*与之对应; H中两点u和v由 边e*相邻当且仅当G 中与顶点u和v对应的面f和g被边e分隔，则称图H称为G的对偶图. 容易看出，平面图G 的对偶图是平面图，平面图的对偶的对偶就是它自己. 对偶图 就是把原来平面图的面变成了它的对偶图的点，两个面相邻对应的就是两个点相邻， 平面图的面染色就变成了它的对偶图的点染色。所以四色问题又可以改成：对任何 一个平面图，都可以用四种颜色对它的点进行染色，使得相邻的两个点之间用不同 的颜色。由于点与点之间的相邻要比面与面之间相邻要更容易辨别，所以下面我们 说的四色问题就是说平面图的点染色
4.欧拉公式：如果一个连通的平面图G有v个顶，点、e条边、f个面，那么 V-e+f=2. 面的度d(f)是指和它关联的边的条数，其中割边被计算两次。这样，所有的面度之 和等于边数的两倍。用d()记一个顶，点的度。根据欧拉公式，有 Σvev(G(2d()-6)+∑feF(G(d()-6)=-6(v-e+f)=-12<0 (1) ∑vev(G(d(w)-6)+∑fefG(2d(0-6)=-6(v-e+)=-12<0 (2 EvEV(G)(d(v)-4)+EfEF(G)(d(f)-4)=-4(v-e+f)=-8<0 (3) 5.五色定理：每个平面图是5-顶，点可染的
4.欧拉公式：如果一个连通的平面图G 有v个顶点、e条边、f个面，那么 v-e+f=2. 面的度d(f)是指和它关联的边的条数，其中割边被计算两次。这样，所有的面度之 和等于边数的两倍。用d(v)记一个顶点的度。根据欧拉公式，有 ∑v∈V(G)(2d(v) − 6) + ∑f∈F(G)(d(f) − 6) = −6(v − e + f) = −12 < 0 (1) ∑v∈V(G)(d(v) − 6) + ∑f∈F(G)(2d(f) − 6) = −6(v − e + f) = −12 < 0 (2) ∑v∈V(G)(d(v) − 4) + ∑f∈F(G)(d(f) − 4) = −4(v − e + f) = −8 < 0 (3) 5.五色定理：每个平面图是5-顶点可染的
6.列表染色：在我们对地图染色时有些国家希望用他们喜欢的颜色（如国旗色) 给自己国家的区域染色，也就是说，图的顶点预先已经给定了一个颜色集合（颜色 的列表)，给某个点染色时必须从这个指定的集合里挑选一个颜色来染这个点，当 然还要是正常染色，这种染色就叫列表染色。下面给出具体的定义：给图的每个顶 点V一个颜色列表L(),如果能从这个列表里挑出一个颜色来染这个点使得最后的 染色是图的一个正常染色，那么就说这个图是L-可染的：如果对任何至少有k个颜色 的L(),都有一个L-染色，则称此图是k-列表可染的。 7.平面图是不是4-列表可染的呢？答案是否定的。 8.平面图是5-列表可染的：下面给出一个更一般的结果！
6.列表染色：在我们对地图染色时有些国家希望用他们喜欢的颜色（如国旗色） 给自己国家的区域染色，也就是说，图的顶点预先已经给定了一个颜色集合（颜色 的列表），给某个点染色时必须从这个指定的集合里挑选一个颜色来染这个点，当 然还要是正常染色，这种染色就叫列表染色。下面给出具体的定义：给图的每个顶 点v一个颜色列表L(v), 如果能从这个列表里挑出一个颜色来染这个点使得最后的 染色是图的一个正常染色，那么就说这个图是L-可染的；如果对任何至少有k个颜色 的L(v)，都有一个L-染色，则称此图是k-列表可染的。 7. 平面图是不是4-列表可染的呢？答案是否定的。 8.平面图是5-列表可染的：下面给出一个更一般的结果！