平面图和色定理.ppt

a b c d f g h x k y a 1 b 1 c 1 2 d f 3 1 h x 3 1 k g 2 2 y 问题：一个平面图的面数是否会随着这个平 面图的不同嵌入而改变？ 证明：对面数 进行归纳证明。由于 是连通的平面图，所以当 时， 是树，因此 。故 假设对于一切面数少于 的所有连通平面图，Euler公式成立。现假设 是一个有 个顶点、 条边和 个面的连通图。由于 ， 至少有一个回路，取这回路中的一条边 ，则 仍是连通平面图，有 个顶点， 条边和 个面，根据归纳假设。 即 证毕。 问题：对于非连通的平面图，其相应的点数、 边数和面数有什么关系？ 推论6.2.4的一般情况： 对简单平面图 ，有 由以上结论，容易验证 和 不是平面图 例：平面上有 个点，其中任意两个点之间的距离至少是1。证明在这 个点中，距离恰好为1的点对数至多是 。 二、平面图与正多面体 凸多面体在平面上的投影是一个连通的平面图，因此Euler公式也适用于凸多面体。为此我们可以用Euler公式讨论正多面体。 定理6.2.6 存在且只存在5种正多面体：正四面体、正方体、正八面体、正十 二面体和正二十面体。 三、平面图的判别 我们可以利用 和 的非平面性来 给出两个有关平面图的判别定理 四、五色定理的证明 我们将利用推论6.2.5的结论来证明每一个平面图的点色数不超过5 证明：设非平面图 的厚度为 ，则存在平面图 ，使 * 6.2 平面图和五色定理 6.2 平面图和五色定理 定义 6.2.1 如果 能与这样的一个图 同构，其中 的顶点在同一个平面上，而 的边只能在端点处相交，就称 为平面图，而称 为 的一个平面嵌入，或称 为 在平面上的实现。 如图 和 就不具有这样的性质。 一、平面图的概念及性质 定义 6.2.2 平面图 的边把整个平面分割成若干各连通的区域，这些区域的闭包称为平面图 的面（包括外部无限区域，称为外部面）。分别用 和 表示 的面的集合和面的个数。 定义6.2.3 用 表示平面图 中围成面 的周界。用 （或 ）表示围成面 的周界的边数，称为 的度。 推论 6.2.2 在任何平面图中，度为奇数的面的个数为偶数。 定理6.2.1 如果G 是平面图，则 定理6.2.3（Euler公式） 设 是一个有 个顶点、 条边和 个面的连通平面图，则 推论6.2.4 若 是阶为 的平面图， 的最短回路的长度为 ，则 证明： 现在对 的每个面 ，由于假设 ，因此 由定理6.2.1知 不妨设该平