二、平面图的特征找出一个图是平面图的充分必要条件的研

二、平面图的特征找出一个图是平面图的充分必要条件的研内容摘要：

, 结论成立。 现设 G有 n个顶点 , 顶点的最大度数是 ,如果删去任一点 v及其关联的边 , 得到 n1个顶点的图G39。 ,它的最大顶点度数 (G39。 ) (G)。 定理 的上界是很弱的 , 例如 G是二分图时 , (G)=2， 而 (G)可以取得相当大。 布鲁克斯 (Brooks)在 1941年证明了这样的结果 , 使  (G)=1+(G)的图只有两类 : 或是奇回路 , 或是完全图。 布鲁克斯定理如下 , 证明从略。 定理 ：如果连通图 G的顶点的最大度数是 (G)， G不是奇回路 ， 又不是完全图 , 则 (G)(G)。  1852 年英国有位青年名叫格思里 (Guthrie),他在画地图时发现 : 如果相邻两国着上不同的颜色 , 那么画任何一张地图只需要四种颜色就够了。 这就是地图的四色问题 一百多年来 , 许多数学家的证明都失败了。  1976 年 6 月美国伊利诺斯大学两位教授阿培尔和哈根使用高速电子计算机 ,花了 1200 多个小时证明了四色问题 ,终于解决了这个大难题。 仍有许多数学家试图用通常证明方法来论证四色问题 , 尚未得到解决。 定义 ：一个没有桥的连通平面图称为 地图 地图可以有自环和多重边。 地图中每一边是两个面的公共边 ,两个面相邻是指这两个面至少有一条公共边 (而不是公共点 ), 并且使相邻两个面着上不同的颜色 , 所以地图是没有桥的。 定义 ：设 G是一个地图 , 对 G的每个面着色 ,使得没有两个相邻的面着上相同的颜色 , 这种着色称为地图的 正常面着色。 地图 G可用 k种颜色正常面着色 ,称 G是 k面可着色的。 使 G的k面可着色的数 k的最小值称为 G的面色数 , 记为 *(G)。 若 *(G)=k,则称 G是 k面色的。 现在地图的四色问题可以叙述为 : 任何地图是 4面可着色的。 对于一个没有自环的平面图 , 它的对偶是一个没有桥的连通平面图 , 即地图。 可以证明一个没有自环的平面图 G的顶点着色问题等价于它的对偶图 G*的面着色问题。 定理 :：设 G是没有自环的平面图 , G*是G的对偶 ,则 G是 k可着色当且仅当 G*是 k面可着色。 证明： (1)设 G是没有自环的平面图 , 则它的对偶 G*没有桥 ， 所以是一个地图。 如果 G是 k可着色的 , 则由于 G*的每个面恰含 G中一个顶点 ,把 G*每个面着上它所包含的顶点的颜色。 因为 G是 k可着色的 ,G中任何两个相。