5
2、欧拉公式（2）
推论1 设G是有v个结点、e条边的连通简单平面图，且v3，则 e3v-6
证：设G的面数为r,当v=3,e=2时，公式成立。当e3时，因G为 简单图，每面的次数不小于3。根据定理1可知，2e3r,即 r2e/3。再应用欧拉公式得：
v-e+2e/32 即 e3v-6。
推论1给出了结点数大于等于3的连通简单平面图应满足的 必要条件，所以可用来判断某些图不是平面图。
将平面图G的一个边不交叉的图画在一个平面上，称为图G 的一个平面表示，也叫做相应于G的地图。
定义2 平面图G的某个平面表示将G所在的平面划分成若干区 域，每个区域叫图G的一个面；包围每个面的边称为该面的 边界；边界上边的条数叫该面的次数，面r的次数记作deg(r)。
面积为无限的面叫无限面，或外部面；面积为有限的面叫 有限面，或内部面。
第7-5讲 平面图
1. 平面图的概念 2. 欧拉公式 3. 库拉托夫斯基定理 4. 课堂练习 5. 第7-5讲 作业
1
1、平面图的概念（1）
定义1 能画在一个平面上且任何两边除端点外互不相交的图称 为平面图。 例：判断下面各图是否为平面图。
(1) (2) (3)是平面图，(4)不是平面图。
2
1、平面图的概念（2）
图(1)有6条边， 4个面，每面次 数皆为3。
图(2)有6条边，有3个面， 各面次数之和为12。
4
2、欧拉公式（1）
定理2 设G是连通平面图，有v个结点，e条边，r个面，则 v-e+r=2 (欧拉公式)
证：对边数用归纳法证明。
若G为平凡图，则v=1,e=0,r=1,公式成立。 若G仅有一条边，则v=2,e=1,r=1,公式成立；或v=1,e=1,r=2,公式仍然成 立。 设G有k条边时公式成立。当G有k+1条边时，设其结点数为v，面数为r， 可分两种情况讨论： (1)如G中有度数为1的结点，删除该结点及其关联的一条边得图G’。显然， G’也是连通平面图，设G’的结点数、边数和面数依次为v’、e’=k、r’，按归 纳假设应满足欧拉公式，即 v’-e’+r’=2，亦即(v-1)-(e-1)+r=2，从而有v-e+r=2。 (2)如G中没有度数为1的结点，则在有限面的边界中删除一条边得图G’。 G’也是连通平面图且边数等于k，按归纳假设应满足欧拉公式，即 v’-e’+r’=2，亦即v-(e-1)+(r-1)=2，从而有v-e+r=2。 综上所述，当边数为k+1时公式成立。定理得证。
deg(r1)=3 deg(r2)=5 deg(r3)=4
图(1)有4个面。
图(2)有3个面。
3
1、平面图的概念（3）
定理1 有限平面图各面次数之和等于边数的2倍。
证：因一条边或是两个面的公共边，或在一个面中作为该面 的边界被计算过两次，所以各面次数之和等于边数的两倍。
deg(r1)=3 deg(r2)=5 deg(r3)=4
2=v-e+r v-e+e/2=v-e/2 即 e2v-4。
推论2给出了各面次数大于等于4的连通平面图应满足的必 要条件，所以可用来判断某些图不是平面图。
例如，应用推论1可知K3，3不 是平面图 。因K3，3是连通平面 图，每个面由四条边围成，v=6, 2v-4=8，而e=9，不满足推论给 出的条件。
12
第7-5讲 作业
P317 3，5
13Leabharlann 93、库拉托夫斯基定理（3）
定理3 （Kuratowski定理）一个图是平面图，当且仅当它不 包含与K3,3或K5在二度结点内同构的子图。 用Kuratowski定理来判断某图是平面图的例子： 证明Petersen图是非平面图。
10
4、课堂练习(1)
练习1 应用欧拉公式证明Petersen图是非平面图。
插入或删除2度结点示意图
8
3、库拉托夫斯基定理（2）
欧拉公式可用来判断某些图不是平面图。但不能用来判断 某图是平面图。波兰数学家给出了一个判断平面图的充分必 要条件。 定理3 （Kuratowski定理）一个图是平面图，当且仅当它不
包含与K3,3或K5在二度结点内同构的子图。
（定理3的证明非常复杂，从略）
11
4、课堂练习(2)
练习2 设G是一个连通平面图，且至少有3个结点。则G必 有一个结点u，使得deg(u)5
证：设G=<V,E>，|V|=v，|E|=e。 假定G的每个结点的度数皆大于6，由握手定理可得2e6v，
所以，e3v>3v-6。这与推论1矛盾。故G至少有一个结点u， 使得deg(u)5。
解：Petersen图中，v=10，e=15，从 图上可以看出，每个面由五边围成， 根据定理7-5.1，有限平面图各面次 数之和等于边数的两倍。 如果Petersen图是平面图，则 2e=5r 所以 r=2e/5=6 但是 v-e+r=10-15+6=12 这说明Petersen图不满足欧拉公式， 故它不是平面图。
7
3、库拉托夫斯基定理（1）
欧拉公式可用来判断某些图不是平面图。但不能用来判断 某图是平面图。波兰数学家Kuratowski给出了一个判断平面 图的充分必要条件。为此，先介绍“在二度结点内同构”的 概念。 定义3 给定图G1、G2，如果它们同构，或通过反复插入或删除
度数为2的之后结点它们同构,则称G1与G2在二度结点内同 构。
例如，应用推论1可知K5不是平面图 (以前从直观上得到过这一结论)。因K5是 连通简单平面图，v=5, 3v-6=9，而e=10， 不满足推论给出的条件。
6
2、欧拉公式（3）
推论2 设G是v个结点、e条边的连通平面图，且G的各面的次数 大于等于4，则e2v-4
证：由所设，G的各面边界边数的总和大于等于4r,这里r为G的 面数。因每边为两个面的边界或作为一个面的边界时按两条边 计算，所以2e4r，即re/2。再应用欧拉公式得：