色，使每个顶点着一种颜色，而同一边的两个不同端点着不同颜色。 定理9.11 任何平面图都是可5-着色的。

习题解答

练习9.2

1、给出图9.19中各面的度，并作一与此图同构的图，使标记2的面在该图的图示中为一无界面。

1 2 3 4

5

6

图9.19 解 面1为2度；面2为3度；面3为3度；面4为8度；面5为5度；面6为1度。 下图与此图同构，且原标记2的面在该图的图示中为一无界面。 235641

2、证明定理9.7，不直接引用定理9.6。 证 由于平面连通简单图每个面的度数至少为3（当n≥3时），故 2m≥3r 又因为n – m + r=2，故 2m≥3(2 – n + m) 即m≤3n – 6

3、证明：有n (n≥3)个顶点，r个面的平面连通简单图满足 r ≤ 2n – 4 证 据定理9.7， m≤3n – 6 又因为n – m + r=2，故

n + r – 2≤3n – 6 即r≤2n – 4 。

4、证明：少于30条边的平面连通简单图至少有一个顶点的度不大于4 。

证 用反证法。假设任一顶点的度均大于或等于5，则5n≤2m＜60，即n＜12。 又因为

5n≤2m≤6n – 12

于是5n≤6n – 12，即n≥12。矛盾。因此至少有一个顶点的度不大于4

6

5、证明：在有6个顶点和12条边的连通平面简单图中，每个面的度均为3。 证 根据欧拉公式n – m + r=2，有

r=2 – n + m=8 故每个面的平均度数为2m / r = 3

又因为连通平面简单图（n≥3）中每个面的度数均大于或等于3，因此该图每个面的度数均为3 。

6、设G为简单无向图，其顶点数n≥11，证明G或G的补G是非平面图。

证 用反证法。假设G和G的补G都是平面图，且G的边数为m，G的边数为m’，则有m≤3n – 6，m’≤3n – 6 （注意，定理9.7对非连通简单平面图同样成立）。进而

m + m’≤6n – 12

又因为 m + m’=n(n – 1)/2，故

n(n – 1)/2≤6n – 12 得3≤n≤10，与n≥11，矛盾。因此G和G的补G中至少有一个是非平面图。

7、证明图9.20中的图都是非平面图。

图9.20 证 (1) 下图中(b)为(a)之子图，而(b)经同胚操作（对虚线内顶点做贯通操作）后为(c)，此乃K3, 3。所以，根据定理9.10，图9.20左图为非平面图。 (a)(b)(c) (2) 同上，下图中(b)为(a)之子图，而(b)经同胚操作（对虚线内顶点做贯通操作）后为(c)，此乃K3, 3。所以，根据定理9.10，图9.20右图为非平面图。 (a)(b)(c) 7

8、作出图9.19的对偶图，再作出你在第一题中所作的平面图的对偶图，并比较这两个对偶图。

解 如下图所示，(a)为9.19的对偶图，(b)为第一题所作平面图的对偶图。经比较可看出两图不同构。 (a)(b) 9、如果平面连通图G的对偶图G*同构于G，则称G为自对偶图，请给出一个自对偶图的例子。 解 10、如果一自对偶图有n个顶点、m条边，证明： m = 2 (n – 1) 证 由于G同构于G*，那么 G的面数r等于其顶点数n。 又因为 n – m + r=2 故m = 2 (n – 1) 。 11、(G*)*未必等同于G，试举例说明之。 解 G(G*)* 12、平面图G称为是完全正则的，如果G的顶点的度都相等，并且G的面的度也相等。 （1）试作出一个完全正则图。 8

*（2）证明：只有五种可能的连通简单图是完全正则的（不算顶点度为1，2的平凡情况）。

解 （1）

证（2）设连通简单图是完全正则的，其各顶点度为j，各面的度为k 。那么

jn?kr?2m又因为 n?m?r?2 故

,m?jnjn ,r?2kn?jnjn??2 2k n(2k?jk?2j)?4k (a) j = 3 时

n(2k?3k?6)?4k

于是 6 – k >0, k可取值为1，2，3，4，5。而k取值为1，2时，不合要求，因此

1）k=3, 则n=4, m=6, r=4 . 2）k=4, 则n=8, m=12, r=6. 3）k=5, 则n=20, m=30, r=12 . (b) j = 4 时

n(2k?4k?8)?4k

于是 4 – k >0, k可取值为1，2，3。而k取值为1，2时，不合要求，因此 4）k=3, 则n=6, m=12, r=8 . (c) j = 5 时

n(2k?5k?10)?4k

于是 10 – 3k >0, k可取值为1，2，3。而k取值为1，2时，不合要求，因此 5）k=3, 则n=12, m=30, r=20 . (c) j = 6 时

n(2k?6k?12)?4k

于是 12 – 4k >0, k可取值为1，2。而k取值为1，2时，不合要求。

当j > 6时，同上可证k<3,不可能构成完全正则的连通简单图。因此，完全正则的连通简单图只有以上五种可能。

13、证明：定理9.9的结论可加强为“至少有3个顶点的度数不大于5”。

证 用反证法。假设度数不大于5的顶点数可以少于3个，但由于n不小于4且为连通图，所以每个顶点的度数最小为1。因此6(n – 2) + 2≤2m。

由于m≤3n – 6，故

6(n – 2) + 2≤2m≤6n – 12，即6n – 10≤6n – 12 矛盾。因而度数不大于5的顶点数至少有3个。

9

14、给出一个平面图，使它是可4-着色的，但不是可3-着色的。 解 15、证明：若图G的最大顶点度数是d，那么G是可(d+1)-着色的。 证 用数学归纳法。 显然，当G的顶点数n≤d+1时，G是可(d+1)-着色的。 设G的顶点数n=k时，G是可(d+1)-着色的，现考虑n=k+1的情况。设v为G中任一点，G’=G – v，则根据归纳假设，G’ 是可(d+1)-着色的。而v的度数不超过d，即与v相邻接的节点所着的颜色不超过d种，则必可以从d+1种颜色中选择一种为d着色，使其与相邻节点均不同色。因此G也是可(d+1)-着色的。 归纳完成，命题得证。 9.3 树

内容提要

9.3.1 树的基本概念

定义9.9 连通无回路的无向图称为无向树，简称为树（tree）。树中的悬挂点又称为树叶（leave），其它结点称为分支点（branched node）。单一孤立结点称为空树（null tree）。诸连通分支均为树的图称为森林（forest），树是森林。

定理9.12 树和森林都是可2-着色的，从而都是二分图。

定理9.13 树和森林都是平面图，其面数为1。

定理9.14 设图T为一树，其顶点数、边数分别是n, m, 那么 n – m = 1 或 m = n – 1

定理9.15 任何多于一个顶点的树都至少有两片叶。 定理9.16 命题“（n，m，）图T为树”与下列5命题中的每一命题等价： （1）T无回路且m = n – 1 。 （2）T连通且m = n – 1 。

（3）T无回路，但添加任一关联T中两顶点的边时，T中产生唯一的一条回路。 （4）T连通，但删去任一边时便不再连通（T的每一边均为割边）。

（5）任意两个不同顶点之间有且仅有一条通路。

9.3.2 生成树

定义9.10 图T称为无向图G的生成树（spanning tree），如果T为G的生成子图且T为树。

定理9.17 任一连通图G都至少有一棵生成树。

定理9.18 设G为连通无向图，那么G的任一回路与G – T(任一生成树T的关于G的补)，至少有一条公共边。

定理9.19 设G为连通无向图，那么G的任一割集与任一生成树至少有一条公共边。 定义9.11 设T为图G的生成树，称T中的边为树枝（branch），称G – T 中的边为弦

10