解 （1）（2）（4）不是平面图，而(3) 是平面图。
平面图
定义8.4.2 设G是一个平面嵌入，G的边将G所在的平面划分 成若干个区域，每个区域称为G的一个面。其中，面积无限的 区域称为无限面或外部面，记成f0，面积有限的区域称为有限 面或内部面，记为f1，f2…，fk 。包围每个面的所有边所构成的 回路称为该面的边界。一个面的边界包含的边数称为该面的次 数，记为deg(f)。
l
deg( fi ) 2e
i0
证明 对图G的每一条边e，若e在两个面的公共边界上，则 在计算这两个面的次数时，e各提供1.当e只在一个面的边界上 出现时，它必在一个面的边界上出现2次，如图 所示，因而 在计算这个面的次数时，e提供2.因此所有面的度数之和等于 边数e的2倍。
欧拉公式
定理8.4.2 设G为任意的连通的平面图，G中有n个结点，e条 边，f个面，则有公式n-e+f=2 成立。该公式称为欧拉公式。
8.4 平面图
定义8.4.1 设G=（V，E）是一个无向图，如果能把G画在 平面上，使得除结点处外，任意两条边都不相交，则称G为平 面图。
将一个平面图G，画成除结点处外，任意两条边都不相交的 和它同构的图，称这样的图为图G的平面嵌入。
例题
判断图8.4.1中的各图是否是平面图。
（1）
（2）
（3）
（4）
定理8.4.9 – 设G是简单图，G的边色数为(G)或(G)+1. – 设G是二分图，G的边色数为(G).
例题
圈图Cn的边色数是多少？ 解 Cn图的结点最大度数( Cn)=2.当n为偶数时，Cn图是二分 图，边色数是( Cn)=2；当n为奇数时，Cn的边色数是3.如图 8.4.9所示，图C4的色数是2，图C5的色数是3。
二分图Km,n图的色数是多少?
四色定理
定理8.4.8(四色定理) 对一个平面图的各个面进行着色,使得 相邻的面有不同的颜色,那么所用的颜色可以不多于4色。
定义8.4.8 对于无环图G的每条边指定一种颜色，使得相邻 的边有不同的颜色，称为对图G的边着色。若能用k种颜色给G 的边着色，则称G是k-可边着色的。若对G的边着色用的最少 颜色数为k，则称G的边色数为k.
证明 对边数e用归纳法。 例8.4.2 假定连通平面图G有30条边，若G的边把图分成20 个区域，则这个图有多少个结点？ 解 根据题意，连通平面图G的边数e=30，面数f=20，代入 欧拉公式n-e+f=2得：
n=2+e-f=2+30-20=12 所以这个图有12个结点。
欧拉公式的推论
推论1 设G是有n （n 3）个结点，e条边，f个面的简单连 通平面图，边数e 3n-6。
欧拉公式的推论
推论2 设G是有n（n 3）个结点，e条边，f个面的简单连通 平面图，若每个面由4条或4条以上的边围成, 则e 2n- 4。
推论3 K5和K3，3都不是平面图。
定理
定理8.4.3 设G是有n个结点，e条边的简单连通平面图，则G 中至少存在一个结点v，使得d（v） 5。
证明 假设G中每个结点v，都有d（v） 6，则由握手定理有 6nd（v）=2e 即有e 3n3n-6，与推论1矛盾。
平面图
f1 v2 v1 f2 f3
v4 v6
v3 f0 v5
面f0的边界回路是一个复杂回路，Deg(f0)=9，面f1的边界回路是环， Deg(f1)=1，面f2和f3的边界回路是简单回路，Deg(f2)=3，Deg(f3)=3
定理
定理8.4.1 一个连通平面图G的边数为e，G的边将G所在的 平面划分成l个面，所有面的次数之和等于边数e的2倍，即
例题
1
1
6
6
2
7
2
7
8
3
9
10
9
4
5
4
1
9
8
3
10 5
4
7
2
6
10 85
3
彼得森图中删去边（7,8）和（4,5）的子图， 和K3，3同胚。 所以彼得森图不是平面图。
8.4.3 对偶图与着色
定义8.4.5 设G是平面图。在图G的每个面中指定一个新结 点，对两个面公共的边，指定一条新边与其相交。由这些新结 点和新边组成的图称为G的对偶图G*。
欧拉公式的推广
定理8.4.4 （欧拉公式的推广）设G为任意的平面图，G有k 个连通分支，n个结点，e条边，f个面，则有公式n-e+f=k+1成 立。
插入和删去结点、同胚
u
v
u wv
uw v
u
v
定义8.4.3 设e=（u，v）是图G的一条边，在G中删去边e， 增加新的结点w，使u，v均与w相邻，则称在图G中插入2度结 点w；设w为G的一个度数为2的结点，w与u，v相邻，删去w及 与w相关联的边(w，u)，(w，v)，同时增加新边(u，v )，则称 在图G中删去2度结点w。
红
红
兰
兰
兰
红
绿
红
兰
例题
某班同学期末共有7门课程考试，课程编号为1到7。已知一 部分同学要参加1、2、6和7四门课程考试，一部分同学要参加 1、2、3和7四门课程考试，一部分同学要参加1、5和6三门课 程考试，一部分同学要参加3、4和7三门课程考试，一部分同 学要参加3、4和5三门课程考试，试问如何安排考试时间，使 得没有学生在同一时间有两门考试？
定义8.4.7 给图G的结点着色所用的最少的颜色数，称为图 G的色数。最少用了k种颜色，则称G是k色图。

定理
定理8.4.6 对于任意的无环图G，G的色数为k，则k(G)+1， (G)是G的结点最大度数。
定理8.4.7（Brooks定理） 对于无环图G，G的色数为k，若 G不是完全图，也不是长度为奇数的基本回路，则k(G)。
对偶图
设n、e、f分别为平面图G的结点数、边数和面数，n*、e*、 f*分别为G的对偶图G*的结点数、边数和面数，按照对偶图的 定义有n*=f, e*=e, f*=n。
着色
定义8.4.6 对一个简单图G进行着色,是指给它的每个结点指 定一种颜色，使得相邻结点都有不同的颜色。若用了k种颜色 给G的结点着色，则称G是k-可着色的。
对这个图的结点着色需要4种颜色，因而 需要安排4个时间段考试
定义8.4.4 若两个图G1和G2同构或通过反复插入或删除2度 结点后是同构的，则称G1和G2是同胚的。
平面图的充分必要条件
定理8.4.5（ 库拉托斯基定理） 设G是无向图，则G是平面 图的充分必要条件是图G不含和K5或K3，3同胚的子图。
推论 设G是无向图，则G是平面图的充分必要条件是图G没 有可收缩为K5或K3，的子图。
给定平面图G，用如下的方法构造G的对偶图G*： – 在G的每一个面fi中任取一个结点vi*作为G*的结点； – 若ek是G的两个面fi和fj的公共边，有一条边ek*=（vi*，vj*）
作为G*的边，且（vi*，vj*）与ek相交； – 若ek只是G的一个面fi的边界时，以fi中的结点vi*为结点做
环ek* ， ek*与ek相交，ek*是G*的一个环。
证明 当n=3，3个结点的简单连通平面图的边数e3f/2, 因此 e 3n-6成立。
当n 3时，G的每个面至少由3条边围成，即每个面的度数 deg(fi) 3, 所以所有面的总度数deg(fi)3f。而deg(fi) =2e , 因而有2e 3f, 即f 2e/3。代入欧拉公式 2= n-e+f n-e+2e/3 有 e 3n-6成立。因此e 3n-6成立。