习题 6

本节对应原书 PDF 第 181–188 页。习题题干逐字取自教材，解答与分析逐字取自答案书《离散数学习题解答与学习指导（第 3 版）》第 6 章；标有「解读」的引用块为 AI 补充的额外直觉。

习题

6.1 无向图 G 如图 6.46 所示.

（1）写出 G 的顶点集 V 和边集 E，并指出 G 的阶数 n 和边数 m 各为多少.

（2）写出各顶点的度数，并验证握手定理及握手定理的推论.

（3）求出 G 的最大度 \Delta 和最小度 \delta.

（4）指出 G 中的平行边、环、孤立点、悬挂顶点与悬挂边.

（5）要使 G 成为简单图，至少要去掉几条边？

6.2 有向图 D 如图 6.47 所示.

（1）写出 D 中各顶点的度数、出度和入度，并验证握手定理.

（2）写出 D 的 \Delta,\Delta^+,\Delta^-,\delta,\delta^+,\delta^-.

（3）D 中有平行边吗？

（4）要使 D 成为简单图，至少要去掉几条边？

6.3 已知无向图 G 的边数 m=13，3 个 2 度顶点，2 个 3 度顶点，1 个 4 度顶点，其余的顶点均为 5 度顶点.试求 G 中 5 度顶点的个数.

6.4 设无向图 G 有 12 条边，已知 G 中有 6 个 3 度顶点，其余顶点的度数均小于 3，问 G 中至少有几个顶点？

6.5 7 阶无向图中，2 度，3 度，4 度，5 度顶点的个数分别为 1,3,2,1.试求 G 的边数 m.

6.6 你能画出一个 7 阶，每个顶点的度数都是 3 的无向图吗？

6.7 （1）请画一个 7 阶无向图 G，使各顶点的度数分别为 1,3,3,4,6,6,7.

（2）证明不存在 7 阶无向简单图 G，以 1,3,3,4,6,6,7 为度数列.

6.8 设 d_1,d_2,\cdots,d_n 为 n 个互不相同的正整数，证明不存在以 d_1,d_2,\cdots,d_n 为度数列的无向简单图.

6.9 设 n 阶图 G 中有 m 条边，证明：

6.10 无向简单图 G_1 与 G_2 如图 6.48 所示，画出它们的补图，G_1 与 G_2 中有自补图（若图 G\cong\overline{G}，则称 G 为自补图）吗？

6.11 证明图 6.49 所示的两个 5 阶无向简单图 G_1 与 G_2 都是自补图.

6.12 设 G 为 n(n\geqslant 2) 阶无向简单图，证明：若 G 为自补图，则 n=4k 或 n=4k+1，其中 k 为正整数.

6.13 设 G_1 与 G_2 都是 n 阶无向简单图，证明：G_1\cong G_2 当且仅当 \overline{G_1}\cong\overline{G_2}.

6.14 已知 5 阶 3 条边的非同构的无向简单图共有 4 个，试问 5 阶 7 条边的非同构的无向简单图共有几个？

6.15 画出 K_4 的 2 条边的所有非同构的生成子图.

6.16 设 G_1,G_2,G_3 均为 4 阶 2 条边的无向简单图，证明它们中至少有两个是同构的.

6.17 3 阶有向完全图的 0,1,2,3,4,5,6 条边的非同构的生成子图各有几个？

6.18 设 G 为 n(n\geqslant 3) 且为奇数）阶无向简单图，证明 G 与 \overline{G} 中奇度顶点个数相等.

6.19 无向图 G 如图 6.50 所示.

（1）G 中最长的圈长为几？最短的圈长为几？

（2）G 中最长的简单回路长度为几？最短的简单回路长度为几？

（3）求出 G 的 \delta,\Delta,\kappa,\lambda.

6.20 有向图 D 如图 6.51 所示.

（1）D 中有多少条非同构的初级回路（圈）？有多少条非同构的简单回路？

（2）求 a 到 d 的短程线和距离.

（3）求 d 到 a 的短程线和距离.

（4）D 是哪类连通图？

6.21 设 G 为 n 阶无向简单图，若 G 不连通，证明 G 的补图 \overline{G} 必连通.

6.22 6 阶 2-正则图有几种非同构的情况？

6.23 已知 3-正则图 G 的阶数 n 与边数 m 满足 m=2n-3，证明 G 只有两种非同构的情况.

6.24 写出图 6.46 的关联矩阵.

6.25 设有向图 D=\langle V,E\rangle，其中 V=\{v_1,v_2,v_3,v_4\}，E=\{e_1,e_2,e_3,e_4,e_5\}，其关联矩阵

如下

求：

（1）各顶点的入度、出度和度数.

（2）平行边.

6.26 有向图 D=\langle V,E\rangle 如图 6.51 所示.

（1）D 中 a 到 d 长度分别为 1,2,3,4,5 的通路各有多少条？

（2）D 中 a 到 d 长度小于等于 3 的通路有多少条？

（3）D 中 a 到自身长度为 1,2,3,4,5 的回路各有多少条？

（4）D 中 d 到自身长度小于等于 3 的回路有多少条？

（5）D 中长度等于 5 的通路（不含回路）有多少条？

（6）D 中长度等于 5 的回路有多少条？

（7）D 中长度小于等于 5 的通路有多少条？其中有多少条是回路？

（8）写出 D 的可达矩阵.

6.27 无向图 G 如图 6.46 所示，求：

（1）a 到 c 长度为 1,2,3,4 的通路数.

（2）a 到自身长度为 1,2,3,4 的回路数.

（3）G 的可达矩阵.

6.28 设无向图 G 中只有两个奇度顶点 u 和 v，证明：u 与 v 必连通.

6.29 设 v 为无环无向图 G 中一条割边的一个端点，证明：v 为割点当且仅当 v 不是悬挂顶点.

6.30 判断图 6.52 所示 3 个图中，哪些是二部图？将是二部图的画出标准形式.

图 6.52

6.31 n 为何值时，圈图 C_n 为二部图？

6.32 n 为何值时，K_n 为二部图？

6.33 为什么轮图 W_n 不是二部图？

6.34 今有甲、乙、丙 3 人去完成任务 a,b,c，已知甲能胜任 a,b,c，乙能胜任 a,b，丙能胜任 b,c. 做二部图 G=\langle V_1,V_2,E\rangle，其中，V_1=\{甲、乙、丙\}，V_2=\{a,b,c\}，E=\{(u,v)\mid u\in V_1,v\in V_2\text{，并且 }u\text{ 能胜任 }v\}. 请画出 G 的图形，并且根据图形给出尽量多

的分配任务方案，使得每个人去完成自己能胜任的一项任务.

6.35 图 6.53 中各二部图是否满足相异性条件？是否满足 t 条件？是否有完备匹配？

图 6.53

6.36 某公司有 6 个部门要招聘员工，限定每位应聘者至多申请 2 个部门，考核结果有 10 人符合条件. 根据这 10 人的申请，每个部门至少有 2 人申请. 问：这 6 个部门是否都能招聘到人？为什么？

6.37 有 4 名学生被录取为硕士研究生：张生，王庆，李民和赵久，有 4 位领导：刘教授，孙教授，周教授和宋教授. 学生报考导师的情况如下：张生报考刘教授和宋教授，王庆报考孙教授和周教授，李民报考刘教授、孙教授和周教授，赵久只报考周教授. 问：4 位教授是否能恰好每人录取一名硕士研究生？

6.38 画出一些无向简单欧拉图，要求

（1）偶数个顶点，偶数条边.

（2）奇数个顶点，奇数条边.

（3）奇数个顶点，奇数条边.

（4）奇数个顶点，偶数条边.

6.39 （1）在什么条件下无向完全图 K_n 为欧拉图？

（2）在什么条件下有向完全图为欧拉图？

（3）在什么条件下轮图 W_n 为欧拉图？

（4）在什么条件下完全二部图 K_{r,s} 为欧拉图？

6.40 （1）在什么条件下无向完全图 K_n 为哈密顿图？

（2）在什么条件下有向完全图为哈密顿图？

（3）在什么条件下 W_n 为哈密顿图？

（4）在什么条件下 K_{r,s} 为哈密顿图？

6.41 画一个简单有向图，使它

（1）既是欧拉图，又是哈密顿图.

（2）是欧拉图，但不是哈密顿图.

（3）不是欧拉图，但是哈密顿图.

（4）既不是欧拉图，也不是哈密顿图.

6.42 证明：有桥的图不是哈密顿图.

6.43 证明：有桥的图不是欧拉图.

6.44 图 6.54 中哪些有欧拉回路？哪些有欧拉通路但无欧拉回路？为什么？

6.45 图 6.55 中哪些有欧拉回路？哪些有欧拉通路但无欧拉回路？为什么？

6.46 图 6.56 中哪些有哈密顿回路？哪些有哈密顿通路但无哈密顿回路？为什么？

6.47 判断图 6.57 所示两个图是否为哈密顿图.

图 6.54

图 6.55

图 6.56

图 6.57

6.48 一名青年生活在城市 A，准备假期到郊区景点 B,C,D 去旅游，然后回到 A. 图 6.58 给出了 A,B,C,D 的位置及它们之间的距离（公里）. 问该青年如何走行程最短？

6.49 某工厂生产由 6 种不同颜色的纱织成的双色布. 已知在品种中，每种颜色至少分别和其他 5 种颜色中的 3 种颜色相搭配. 证明可以挑出 3 种双色布，它们恰有 6 种不同的颜色.

6.50 求图 6.59 所示非连通的平面图各面的次数，并验证定理 6.15（即各面次数之和等于边数的两倍）.

6.51 试将图 6.60 所示的平面图的内部面 R_1 变成外部面.

6.52 证明图 6.61 所示无向图为极大平面图.

6.53 若 G 是一个非平面图并且任意删除一条边后都是平面图，则称 G 是极小非平面图. 试给出两个 7 阶的非同构的极小非平面图.

图 6.58

图 6.59

图 6.60

图 6.61

6.54 已知 7 阶连通平面图 G 有 6 个面，试求 G 的边数 m.

6.55 已知具有 3 个连通分支的平面图 G 有 4 个面，9 条边，求 G 的阶数 n.

6.56 证明图 6.62 所示两个图均为非平面图.

图 6.62

图 6.63

6.57 证明图 6.63 所示无向图为平面图.

6.58 画出轮图 W_5 的对偶图 W_5^*，并证明 W_5\cong W_5^*.

6.59 G 为 n 阶 m 条边，每个面的次数至少为 4 的连通的平面图，证明：m\leqslant 2n-4.

6.60 给下列各图的顶点着色最少要用多少种颜色？

（1）7 阶圈图 C_7.

（2）8 阶圈图 C_8.

（3）9 阶轮图 W_9.

（4）10 阶轮图 W_{10}.

（5）n 阶完全图 K_n.

（6）二部图 K_{r,s}.

6.61 给图 6.56 中各图用尽量少的颜色着色.

6.62 某大学计算机专业三年级有 5 门选修课，其中课程 1 与 2,1 与 3,1 与 4,2 与 4,2 与 5,3 与 4,3 与 5 均有人同时选修. 问安排这 5 门课的考试至少需要几个时间段？

6.63 假设当两台无线发射设备的距离小于 200 公里时不能使用相同的频率. 现有 6 台设

备，表 6.1 给出它们之间的距离，问：它们至少需要几个不同的频率？

表 6.1

6.64 有 6 名博士生要进行论文答辩，答辩委员会的成员分别为 A_1=\{张教授，李教授，王教授\}，A_2=\{李教授，赵教授，刘教授\}，A_3=\{张教授，刘教授，王教授\}，A_4=\{赵教授，刘教授，王教授\}，A_5=\{张教授，李教授，孙教授\}，A_6=\{李教授，刘教授，王教授\}，那么这次论文答辩必须安排在多少个不同的时间？

习题解答与分析

6.1 设图 6.1 所示无向图为 G=\langle V,E\rangle.

（1）V=\{a,b,c,d,e,f\}. E 中元素有两种表示法.

① 定义意义下：E=\{(a,b),(b,b),(b,c),(c,d),(c,d),(d,e)\}.

② 令 e_1=(a,b)，e_2=(b,b)，e_3=(b,c)，e_4=(c,d)，e_5=(c,d)，e_6=(d,e)，则 E=\{e_1,e_2,e_3,e_4,e_5,e_6\}.

G 的阶数 n=|V|=6，G 的边数 m=|E|=6.

（2）d(a)=1，d(b)=4，d(c)=3，d(d)=3，d(e)=1，d(f)=0. 各顶点度数之和为 12，它正是边数 m(=6) 的两倍. 奇度数顶点为 4 个（为偶数）.

（3）按字母顺序，得 G 的度数列为 1,4,3,3,1,0，其中最大度 \Delta=4，在 b 点达到，最小度 \delta=0，在 f 点达到.

（4）顶点 c,d 之间有两条平行边（e_4 与 e_5），顶点 b 处有一个环（e_2），f 为孤立点，a,e 均为悬挂点，它们关联的边 e_1 与 e_6 为悬挂边.

（5）要使 G 成为简单图，至少要去掉 2 条边. 在这里，e_2 一定去掉，e_4 与 e_5 中至少要去 1 条.

6.2 设图 6.2 所示有向图为 D=\langle V,E\rangle.

（1）V=\{a,b,c,d\}，E=\{\langle a,b\rangle,\langle b,b\rangle,\langle b,c\rangle,\langle c,d\rangle,\langle d,c\rangle,\langle d,a\rangle,\langle a,d\rangle,\langle a,c\rangle\}，也可表示为 E=\{e_1,e_2,\cdots,e_8\}. 其中，e_1=\langle a,b\rangle，e_2=\langle b,b\rangle，e_3=\langle b,c\rangle，e_4=\langle c,d\rangle，e_5=\langle d,c\rangle，e_6=\langle d,a\rangle，e_7=\langle a,d\rangle，e_8=\langle a,c\rangle.

各顶点的度数、出度、入度分别为

易知，各顶点的度数之和为 16，它等于边数 m(=8) 的两倍，且各顶点入度之和与出度之和

均为边数 m.

（2）从（1）中结果可以看出：

D 的最大度与最小度相等，即 \Delta=\delta=4，在 a,b,c,d 顶点处达到.

D 的最大出度 \Delta^{+}=3，在 a 点处达到.

D 的最小出度 \delta^{+}=1，在 c 点处达到.

D 的最大入度 \Delta^{-}=3，在 c 点处达到.

D 的最小入度 \delta^{-}=1，在 a 点处达到.

（3）D 中无平行边，注意 \langle c,d\rangle 与 \langle d,c\rangle 不是平行边，同样地，\langle a,d\rangle 与 \langle d,a\rangle 也不是平行边.

（4）要使 D 成为简单图，至少去掉 1 条边，此边为环 \langle b,b\rangle.

6.3 G 中有 2 个 5 度顶点.

分析 用握手定理解本题. 设 5 度顶点有 x 个，由握手定理可知：

可解出 x=2，即 G 中有 2 个 5 度顶点. 可设 G 的度数列为 d，则 d 为

以 d 为度数列的无向图有许多种非同构的情况，在图 6.19 中给出的两个图都以 d 为度数列，它们是非同构的.

6.4 G 中至少有 9 个顶点.

分析 用握手定理解本题. 设 G 有 n 个顶点 v_1,v_2,\cdots,v_n，不妨设 d(v_1)=d(v_2)=\cdots=d(v_6)=3，而 d(v_7),\cdots,d(v_n) 均小于等于 2. 由握手定理可知：

6.5 边数 m=12.

解答与分析 设 7 阶无向图 G 的边数为 m. 由握手定理可知：

7 阶 12 条边的无向图 G 的度数列 d 为

以 d 为度数列的 7 阶图，也有许多非同构的情况，图 6.20（a）、（b）所示的 7 阶简单图均以 d 为度数列，它们是非同构的.

图 6.20

6.6 根据握手定理的推论，不能画出一个 7 阶且每个顶点的度数都是 3 的无向图.

6.7 （1）图 6.21(a)和(b)两个非同构的图都满足要求.

（2）用归谬法（即反证法）证明之.

假设存在 7 阶无向简单图 G，以 1,3,3,4,6,6,7 为度数列，则 \Delta(G)=7，这与 n 阶无向简单图的最大度 \Delta\leqslant n-1 相矛盾.

图 6.21

6.8 利用 n 阶无向简单图 G 的最大度 \Delta(G)\leqslant n-1 证明本题.

用归谬法证明. 假设存在以 d_1,d_2,\cdots,d_n(d_1,d_2,\cdots,d_n 为 n 个互不相同的正整数)为度数列的无向简单图 G=\langle V,E\rangle，V=\{v_1,v_2,\cdots,v_n\}，不妨设 d(v_i)=d_i，i=1,2,\cdots,n，则

这与 n 阶无向简单图的最大度应该 \leqslant n-1 相矛盾.

6.9 用握手定理以及图的最大度与最小度的概念证明本题.

设 G 的顶点集 V=\{v_1,v_2,\cdots,v_n\}，易知

从而有

由握手定理可知，2m=\sum_{i=1}^{n}d(v_i)，于是有

其实，由握手定理可知，\frac{2m}{n} 是 G 的各顶点度数的平均值，因而必有

6.10 图 6.3 中 G_1 的补图 \overline{G_1} 为图 6.22(a)所示，G_1 与 \overline{G_1} 都是 4 阶长度为 3 的路径，所以 G_1\cong\overline{G_1}，因此 G_1 是自补图（当然 \overline{G_1} 也是自补图）.

图 6.3 中 G_2 的补图 \overline{G_2} 为图 6.22(b)所示，G_2 是 4 阶非连通图，而它的补图 \overline{G_2} 是 4 阶连通图，当然必有 G_2\not\cong\overline{G_2}，所以 G_2 不是自补图.

6.11 图 6.23(a)所示的图为图 6.4 中 G_1 的补图 \overline{G_1}，G_1 与 \overline{G_1} 都是 5 阶圈，因而 G_1\cong\overline{G_1}，故 G_1（\overline{G_1}）为自补图.

图 6.23(b)所示的图为图 6.4 中 G_2 的补图 \overline{G_2}，G_2 与 \overline{G_2} 都是由一个 K_3 带着两条悬挂边构成的 5 阶无向简单图，G_2\cong\overline{G_2}，所以 G_2（\overline{G_2}）为自补图.

图 6.22

图 6.23

6.12 本题分下面几步证明（使用直接证明法）.

（1）由补图的定义可知

设 G 与 \overline{G} 的边数分别为 m_1 和 m_2，则

（2）由于 G 为自补图，所以 G\cong\overline{G}，因而 m_1=m_2，记 m_1=m_2=m. 于是有

（3）由于 n 与 (n-1) 是连续的自然数，所以 n 与 (n-1) 互素，又因为 m 是整数，必有下面两种情况：

情况 1 n=4k(k\geqslant 1)，例如 6.10 题中，图 6.3 中的 G_1 为自补图，n=4(k=1 的情况).

情况 2 n-1=4k，即 n=4k+1(k\geqslant 1). 例如 6.11 题中，图 6.4 中 G_1 为自补图，n=5（是 k=1 的情况）.

注意 若 G 是 n 阶自补图，则 n=4k 或 n=4k+1 是必要条件，而不是 G 为自补图的充分条件，图 6.3 中的 G_2 满足 n=4k 的条件，但不是自补图.

6.13 用图同构及补图的定义证明本题.

证明：若 G_1\cong G_2，则 \overline{G_1}\cong\overline{G_2}.

设 V(G_1)=V(\overline{G_1})=V_1，V(G_2)=V(\overline{G_2})=V_2，再令 E(G_1),E(\overline{G_1}),E(G_2),E(\overline{G_2}) 分别为 G_1,\overline{G_1},G_2,\overline{G_2} 的边集.

因为 G_1\cong G_2，所以存在双射函数 f:V_1\to V_2，使得 \forall u,v\in V_1，(u,v)\in E(G_1)\Leftrightarrow(f(u),f(v))\in E(G_2). 于是，对此 f，必有 (u,v)\notin E(G_1)\Leftrightarrow(f(u),f(v))\notin E(G_2)，这又蕴涵着：(u,v)\in E(\overline{G_1})\Leftrightarrow(f(u),f(v))\in E(\overline{G_2})，从而可知，\overline{G_1}\cong\overline{G_2}.

类似可证明，若 \overline{G_1}\cong\overline{G_2}，则 G_1\cong G_2.

从以上的证明过程可知，设 G_1 与 G_2 都是 n 阶无向简单图，则 G_1\not\cong G_2 当且仅当 \overline{G_1}\not\cong\overline{G_2}.

6.14 已知 5 阶 3 条边的非同构的无向简单图共有 4 个，则 5 阶 7 条边的非同构的无向简单图也共有 4 个.

分析 若 G 是 n 阶 m 条边的无向简单图，则 G 的补图 \overline{G} 是 n 阶 n(n-1)/2-m 条边的无向简单图. 当 n=5，m=3 时，则 \overline{G} 是 5 阶 7 条边的无向简单图.

由上题（题 6.13）的讨论可知，G_1\cong G_2 当且仅当 \overline{G_1}\cong\overline{G_2}（G_1\not\cong G_2 当且仅当 \overline{G_1}\not\cong\overline{G_2}）. 设 5 阶 3 条边的 4 个非同构的无向简单图分别为 G_1,G_2,G_3,G_4，它们的补图分别为 \overline{G_1},\overline{G_2},\overline{G_3},\overline{G_4} 也彼此分别不同构，并且 5 阶 7 条边的非同构的无向简单也只有以上 4 个.

若能找出 5 阶 3 条边的 4 个非同构的无向简单图，根据补图的定义，马上可找出它们的补图，这比直接找 5 阶 7 条边所有非同构的无向简单图要方便得多.

下面给出通过画出 5 阶 3 条边所有非同构的无向简单图，画出 5 阶 7 条边的所有非同构的无向简单图的过程.

（1）5 阶 3 条边所有的无向简单图都是 K_5 的子图. 3 条边共产生 6 度（握手定理），将 6 度分配给 5 个顶点，按简单图的要求共有 4 种分配方案：

① 1,1,1,1,2；

② 0,1,1,2,2；

③ 0,1,1,1,3；

④ 0,0,2,2,2.

每种方案产生一个非同构的 5 阶 3 条边的简单图，而 4 个图是彼此非同构的，所产生的 4 个图由图 6.24(a)、(b)、(c)、(d)所示.

图 6.24

（2）4 个 5 阶 7 条边的非同构的无向简单图分别为图 6.24 中各图的补图，见图 6.25 中各图所示.

6.15 K_4 的两条边的非同构的生成子图共有 2 个. 由握手定理可知，两条边共产生

图 6.25

4 度，分配给 4 个顶点，其分配方案为

① 1,1,1,1；

② 0,1,1,2.

它们对应的生成子图为图 6.26(a)和(b)所示.

图 6.26

6.16 利用 6.15 题和鸽巢原理解此题. 形象地说，鸽巢原理为：m 只鸽子飞入 n 个鸽巢，则至少存在一个鸽巢至少飞入 \left\lceil\frac{m}{n}\right\rceil 只鸽子. 关于 \lceil x\rceil 见主教材 1.1.2 节. 例如，当 m=5，n=2 时，则至少有 \left\lceil\frac{5}{2}\right\rceil=3 只鸽子飞入同一个鸽巢. 当 m=8，n=5 时，则至少有 \left\lceil\frac{8}{5}\right\rceil=2 只鸽子飞入同一个鸽巢. 下面证明本题.

4 阶无向简单图，在同构意义下都是 K_4 的生成子图. 由上题（题 6.15）可知，K_4 的 2 条边的生成子图只有两个是非同构的. G_1,G_2,G_3 都是 4 阶 2 条边的无向简单图，在同构意义下，它们都是 K_4 的生成子图，由鸽巢原理可知，G_1,G_2,G_3 中至少有两个是同构的.

在有些问题中，灵活地应用鸽巢原理，会带来很大的方便.

6.17 3 阶有向完全图的 0,1,2,3,4,5,6 条边的非同构的生成子图的个数分别为 1,1,4,4,4,1,1. 在图 6.27 中分别给出了它们的图形. 0 条边、1 条边、5 条边、6 条边的分别由图 6.27(a)、(b)、(c)、(d)所示；2 条边的 4 个图分别由图 6.27(e)、(f)、(g)、(h)所示；3 条边的 4 个图分别由图 6.27(i)、(j)、(k)、(l)所示；4 条边的 4 个图分别由图 6.27(m)、(n)、(o)、(p)所示.

图 6.27

图 6.27（续）

6.18 利用 n 阶无向简单图 G，G 的补图 \overline{G}，无向完全图 K_n 的性质及相互之间的关系证明本题.

设 G,\overline{G},K_n 的顶点集分别为 V(G),V(\overline{G}),V(K_n)，由 G,\overline{G},K_n 之间的关系可知，V(G)=V(\overline{G})=V(K_n)，并记它们都等于 V. \forall v\in V，记 v 在 G,\overline{G},K_n 中的度数分别为 d_G(v),d_{\overline{G}}(v),d_{K_n}(v)，则必有

由于 n 为奇数，所以 n-1 为偶数，因而，若 d_G(v) 为奇数，必有 d_{\overline{G}}(v) 为奇数，于是 G 与 \overline{G} 中奇度顶点个数必相等.

解读：原书的图 6.1～图 6.18 是答案书给教材插图重新编的号，与教材的图 6.46～图 6.63 一一对应；读解答时把答案书的图号按出现顺序对回教材图号即可。

6.19 为了回答本题中的问题，将图 6.5 的顶点和边标定，使其成为标定图，见图 6.28 所示.

图 6.28

（1）G 中最长的圈长为 4，最短的圈长为 1. 图 6.28 中，v_1e_3v_6e_7v_5e_5v_2e_2v_1 是长度为 4 的圈，而 v_1e_1v_1（环）为长度为 1 的圈.

（2）最长的简单回路的长度为 10，最短的简单回路的长度为 1. v_1e_1v_1e_2v_2e_4v_6e_5v_2e_6v_3e_8v_4e_{11}v_5e_9v_3e_7v_6e_3v_1 为最长的一条简单回路，v_1e_1v_1 为最短的简单回路.

注意 初级回路（圈）都是简单回路，但反之不真.

待核：答案书 p116 该行被图 6.28 版面压盖，最长简单回路的顶点序列已按放大后的字面抄录；若与答案书原版有出入，以原书为准.

（3）G 的最小度 \delta=3（在顶点 v_4,v_5 达到）；

G 的最大度 \Delta=4（在顶点 v_1,v_2,v_3,v_6 达到）；

G 的点连通度 \kappa=1（G 有割点 v_1）；

G 的边连通度 \lambda=2（\{e_2,e_3\}，\{e_6,e_7\} 等为边割集）.

6.20 （1）D 中有 3 条非同构的圈，有 4 条非同构的简单回路.

（2）a 到 d 的短程线为 aed，d\langle a,d\rangle=2.

（3）d 到 a 的短程线为 deba，d\langle d,a\rangle=3.

（4）D 是单向连通图.

分析 （1）对于初级回路（圈）C_1 与 C_2 来说，C_1\cong C_2 当且仅当 C_1 与 C_2 长度相等，但对于简单回路来说却没有以上性质. 图 6.6 所示有向图 D 中，有 3 条初级回路非同构，它们的长度分别为 1,2,3. 将它们独立画出来，见图 6.29(a)、(b)、(c)所示. D 中非同构的简单回路，除以上 3 条外，还有一条长度为 5 非圈简单回路，见图 6.29(d)所示，所以 D 中共有 4 条非同构的简单回路.

图 6.29

现在要问，若不是同构意义下，而是在定义意义下，图 6.6 所示有向图 D 中有多少条不同的初级回路（圈）？又有多少条不同的简单回路呢？

在定义意义下，不同始点（终点）的回路看成是不同的. 在 D 中，长度为 1 的圈还是一条，即 c 处的环. 长度为 2 的有 2 条：ede 和 ded. 长度为 3 的有 6 条：aeba，ebae，baeb，bdeb，debd，ebde. 所以，定义意义下，D 中共有 9 条初级回路. 而对简单回路来说，除了以上 9 条以外，还有 aedeba，edebae，debaed，baedeb，所以，定义意义下，D 中共有 13 条简单回路. 在图比较复杂时，用观察法很难求出 D 中的定义意义下的通路数与回路数，这就要用邻接矩阵及各次幂来求解了.

（2）D 中 a 到 d 的短程线是唯一的，即为 aed，d\langle a,d\rangle=2.

（3）D 中 d 到 a 的短程线也是唯一的，即为 deba，d\langle d,a\rangle=3.

（4）D 中存在经过每个顶点至少一次的通路，如 aebdc 就是其中的一条，所以是单向连通的，但 D 中无经过每个顶点至少一次的回路，所以 D 不是强连通的.

6.21 使用直接证明法证明.

设 G 与 \overline{G} 对应的完全图为 K_n. V(G) 与 V(\overline{G}) 分别为 G 与 \overline{G} 的顶点集，易知 V(G)=V(\overline{G})=V(K_n)，设它们为 V. 又设 E(G) 与 E(\overline{G}) 分别为 G 与 \overline{G} 的边集，则 E(G)\cap E(\overline{G})=\varnothing，且 E(G)\cup E(\overline{G})=E(K_n). 设 G 有 k(k\geqslant 2) 个连通分支 G_1,G_2,\cdots,G_k. 下面证明 \overline{G} 连通，又只需证明，\forall u,v\in V(\overline{G})，u\sim v，即 u 到 v 有通路，分以下两种情况讨论.

（1）u 与 v 在 G 的同一连通分支 G_r(1\leqslant r\leqslant k) 中，则对于 G 的任一个另外的连通分支 G_s(s\neq r) 中的任一个顶点 w，根据补图的定义，必有 (u,w),(v,w)\in E(\overline{G})，于是在 \overline{G} 中，u 到 v 有通路 uwv，所以，u\sim v.

（2）u 与 v 在 G 的不同连通分支 G_i 与 G_j(i\neq j) 中，如 u 在 G_i 中，v 在 G_j 中，由补图定义可知，(u,v)\in E(\overline{G})，所以 u\sim v.

综上所述，若 G 不连通，则 \overline{G} 必连通.

说明 其实，若 G 不连通，则 G 必连通. 当然也可能 G 与 \overline{G} 都连通. 所以，结论应该是，G 与 \overline{G} 至少有一个是连通的.

6.22 6 阶 2-正则图只有两种非同构的情况.

分析 由于正则图都是简单图，所以 6 阶 2-正则图中不可能有长为 1 的圈（环），也不可能有长为 2 的圈（由两条平行边构成）.

设 G 为 6 阶 2-正则图，其顶点集为 V. \forall v\in V，由于 d(v)=2，又 G 为简单图，因而必 \exists v_j,v_k\in V，且 j\neq k，j\neq i，k\neq i，使得 (v_j,v_i)\in E(G)，(v_i,v_k)\in E(G)，形成为长为 2 的路径 v_jv_iv_k. 下面分两种情况讨论.

（1）v_j 与 v_k 相邻，得一个 3 阶圈 v_jv_iv_kv_j. G 中另外 3 个顶点中的任一个都不能与这个 3 阶圈上的顶点相邻了，否则会出现度数 \geqslant 3 的顶点. 并且，另外 3 个顶点也必然形成 3 阶圈，于是 G 由两个 3 阶圈组成.

（2）v_j 与 v_k 不相邻，此时，必存在 v_i,v_j,v_k 外的顶点，如 v_l 与 v_j 或 v_k 相邻，不妨设 v_l 与 v_k 相邻，形成长度为 3 的路径 v_jv_iv_kv_l，这时，v_j 与 v_l 不能相邻，否则形成 4 阶圈 v_iv_jv_lv_kv_i，圈外的两个顶点不能与圈上的顶点相邻，彼此相邻后又均只能是 1 度顶点. 所以只能是 6 个顶点构成一个 6 阶圈 v_jv_iv_kv_lv_sv_tv_j.

综上所述，6 阶 2-正则图只能有两种非同构的情况，见图 6.30(a)、(b)所示. 它们都是 K_6 的生成子图.

6.23 利用题 6.13 和题 6.22 证明本题.

首先求解 n 和 m. 由已知条件可得方程组

解出 n=6，m=9，所讨论的图都是 6 阶 9 条边的 3-正则图，它们都是 K_6 的生成子图. 这些图的补图都是 6 阶 2-正则图. 由 6.22 题可知，6 阶 2-正则图只有两种非同构的情况，由题 6.13 可知，6 阶 3-正则图也只有两种非同构的情况，见图 6.31(a)、(b)所示，它们分别与图 6.30(a)、(b)互为补图.

图 6.30

图 6.31

6.24 首先给图 6.1 的边标记，如图 6.32 所示. 它的关联矩阵为

待核：答案书 p118 印出的关联矩阵为 5 行 6 列，而图 6.1（教材图 6.46）有 6 个顶点 6 条边；此处按答案书字面照抄，未作补齐.

图 6.32

6.25 （1）d^{+}(v_1)=4，d^{-}(v_1)=0，d(v_1)=4，d^{+}(v_2)=1，d^{-}(v_2)=1，d(v_2)=2，d^{+}(v_3)=0，d^{-}(v_3)=3，d(v_3)=3，d^{+}(v_4)=0，d^{-}(v_4)=1，d(v_4)=1.

（2）e_4 与 e_5 是平行边.

6.26 先写出 D 的邻接矩阵和它的 2\sim 5 次幂.

（1）a 到 d 长度为 1,2,3,4,5 的通路分别为 0 条，1 条，1 条，1 条，3 条.

（2）a 到 d 长度小于等于 3 的通路为 2 条.

（3）a 到 a 长度为 1,2,3,4,5 的回路分别为 0 条，0 条，1 条，0 条，1 条.

（4）d 到 d 长度小于等于 3 的回路为 2 条.

（5）D 中长度等于 5 的通路（不含回路）共 51 条.

（6）D 中长度等于 5 的回路共 11 条.

（7）D 中长度小于等于 5 的通路共 151 条，其中回路 25 条.

（8）由 p_{ij}=1 当且仅当 a_{ij}^{(1)}+a_{ij}^{(2)}+a_{ij}^{(3)}+a_{ij}^{(4)}>0，i\neq j，可达矩阵为

分析 用邻接矩阵计算的有向图的通路数和回路数都是在定义意义下的，一个长度为 k 的回路在定义意义下是 k 条回路.

6.27 写出它的相邻矩阵及 2\sim 4 次幂.

（1）a 到 c 长度为 1,2,3,4 的通路分别有 0 条、1 条、1 条、7 条.

（2）a 到自身长度为 1,2,3,4 的回路分别有 0 条、1 条、1 条、3 条.

（3）注意到 f 是孤立点，初级通路最长为 4，由 A+A^{2}+A^{3}+A^{4}，G 的可达矩阵

6.28 用握手定理的推论证明本题，使用归谬法比较方便.

设 G 的两个奇度顶点分别为 u 和 v. 若 u 与 v 不连通，即它们之间无通路，则 u 与 v 必处于 G 的不同连通分支中，不妨设 u 在 G 的连通分支 G_1 中，v 在 G_2 中，由于 G 中只有两个奇度顶点，于是 G_1 与 G_2 中均各有一个奇度顶点，当对 G_1 与 G_2 使用握手定理推论时，都会引出矛盾，所以奇度顶点 u 与 v 必处于 G 的同一个连通分支中，即它们之间必有通路，也即它们必连通.

6.29 设 e 为与 v 关联的割边（桥）.

先证明：若 v 为割点，则 v 不是悬挂顶点（1 度顶点），用归谬法证明之. 否则，若 v 是悬挂顶点，则从 G 中删除 v，只是将 v 及关联割边 e 从 G 中去掉了，因而 p(G-v)=p(G)，即从 G 中删除 v，所得图 G-v 与 G 的连通分支数相同，这与 v 为割点相矛盾.

再证明：若 v 不是悬挂顶点，则 v 为割点. 由于 v 不是 1 度顶点，因而 v 除与割边 e 关联外，还必须与另外一些边，比如 e_1,e_2,\cdots,e_r 相关联，当从 G 中删除 v 时，e,e_1,e_2,\cdots,e_r 全被删除，可是 e 是割边，因而 p(G-v)>p(G)，所以 v 为割点.

6.30 图 6.7(a)、(b)所示的图为二部图，而图 6.7(c)所示的图不是二部图.

一个无向图 G 是二部图当且仅当 G 中无奇长回路. 图 6.7(a)、(b)所示图中无奇长回路，而图 6.7(c)所示图中，bcgfdb 与 bdfeab 都是长为 5 的回路. 图 6.7(a)、(b)所示二部图的标准形式分别由图 6.33(a)、(b)所示.

图 6.33

解读：判断二部图只需看有没有奇长回路，而不用去试两种颜色——因为「二部」与「2-可着色」是同一件事，一个奇圈无论怎么染都必然撞色。

6.31 当 n=2k(k\in N\wedge k\geqslant 2) 时，圈图 C_n 为二部图.

分析 图 G 为二部图当且仅当 G 中不含奇圈. 因而要求 n 为偶数，又因为在圈图定义中，要求 n\geqslant 3，所以圈图为二部图当且仅当 n 为大于等于 4 的偶数.

6.32 n=1 或 n=2 时 K_n 为二部图.

分析 平凡图为二部图，所以 K_1 为二部图，K_2 中无奇长回路，所以 K_2 为二部图. 而当 n\geqslant 3 时，K_n 中均含奇圈（如 K_3 是 K_n(n\geqslant 3) 的子图），所以当 n\geqslant 3 时，K_n 都不是二部图.

6.33 根据轮图 W_n 的定义可知，n\geqslant 4，因而任何轮图中都含 K_3，即都含长度为 3 的圈，所以 W_n 不是二部图.

6.34 图 G 的图形如图 6.34(a)所示. 每一个完美匹配给出一个分配方案，共有 3 种不同的分配方案：

方案 1 甲完成 a，乙完成 b，丙完成 c；

方案 2 甲完成 b，乙完成 a，丙完成 c；

方案 3 甲完成 c，乙完成 a，丙完成 b.

对应的匹配是

方案 1 M_1=\{(甲,a)，(乙,b)，(丙,c)\}，见图 6.34(b)所示；

方案 2 M_2=\{(甲,b)，(乙,a)，(丙,c)\}，见图 6.34(c)所示；

方案 3 M_3=\{(甲,c)，(乙,a)，(丙,b)\}，见图 6.34(d)所示.

图 6.34

6.35 在图 6.8 中，图(a)满足相异性条件，但不满足 t 条件. 有完备匹配，并且是完美匹配. 图(b)不满足相异性条件，u_1,u_2,u_4 只与 v_1,v_4 关联. 反过来，v_2,v_3 只与 u_3 关联. 当然也不满足 t 条件. 不存在完备匹配. 图(c)满足 t(t=2) 条件，当然也满足相异性条件. 有完备匹配，但不是完美匹配.

分析 满足相异性条件是存在完备匹配的充分必要条件，而满足 t 条件是存在完备匹配的充分条件. 不满足相异性条件一定也不满足 t 条件，满足 t 条件也一定满足相异性条件.

6.36 作二部图 G=\langle V_1,V_2,E\rangle，其中 V_1 是 6 个部门，V_2 是 10 位应聘者，部门 u 与应聘者 v 相邻当且仅当应聘者 v 申请部门 u. 根据题设，V_1 的每个顶点至少关联 2 条边，V_2 的每个顶点至多关联 2 条边. G 满足 t(t=2) 条件，存在 V_1 到 V_2 的完备匹配，故这 6 个部门都能招聘到人.

6.37 作二部图 G=\langle V_1,V_2,E\rangle，其中 V_1=\{张生，王庆，李民，赵久\}，V_2=\{刘教授，孙

图 6.35

教授，周教授，宋教授\}，E=\{(u,v)\mid u\in V_1,v\in V_2，且 u 报考 v\}，如图 6.35 所示.

不难看出 \{(张生，宋教授)，(王庆，孙教授)，(李民，刘教授)，(赵久，周教授)\} 是一个完美匹配，它恰好给出每位教授录取一名硕士研究生的分配方案.

6.38 本题所要求的无向简单欧拉图很多，每种都可以给出若干族图.

（1）给定一个 n(n 为 \geqslant 4 的偶数)阶偶圈 C_n，使 C_n 上的每个顶 v_i(i=1,2,\cdots,n) 都成为 C_n 与另一个阶数 \geqslant 4 的偶圈的公共顶点，则所得图具有偶数个顶点，偶数条边，且为欧拉图. 当 n=4，另外 4 个偶圈的阶数分别为 4,4,4,6 的图如图 6.36(a)所示.

（2）在（1）中给出的图族中，只需将 C_n 上的某一个顶点（只一个顶点）所共用的偶圈改成长度 \geqslant 3 的奇圈，就得到一个奇数个顶点、奇数条边的简单欧拉图. 图 6.36(b)所示的图就是其中的一个.

（3）设 C_n(n\geqslant 3 的奇数)为 n 阶奇圈，让 C_n 上每个顶点都共用一个偶圈（阶数 \geqslant 4），所得简单图为偶数个顶点、奇数条边的欧拉图. 图 6.36(c)所示就为其中的一个.

（4）类似可定义一族图是奇数个顶点、偶数条边的简单欧拉图，图 6.36(d)所示的图是一个特例.

图 6.36

6.39 （1）n 为奇数（即 n=2k+1，k\in N）时，K_n 为欧拉图. 此时，K_n 的各顶点的度数均为 2k.

（2）任何阶有向完全图都是欧拉图.

（3）任何阶轮图都不是欧拉图. 若 n 为奇数，则 W_n 中有 n-1 个奇度顶点，而当 n 为偶数时，W_n 中无偶度顶点，所以 W_n 不是欧拉图.

（4）当 r\geqslant 2，s\geqslant 2，且 r,s 均为偶数时，K_{r,s} 为欧拉图.

6.40 （1）除 K_2 不是哈密顿图外，K_n(n\neq 2) 全是哈密顿图. 注意：平凡图是哈密顿图，所以 K_1 是哈密顿图. 当 n\geqslant 3 时，K_n 中均有长度为 n 的圈，这些圈均为 K_n 中的哈密顿回路.

（2）任何阶的有向完全图都是有向哈密顿图，平凡有向图是哈密顿图.

（3）轮图 W_n 都是哈密顿图. 在轮图的定义中，已规定 n\geqslant 4，因而在 W_n 中都存在 n 阶圈（生成圈），所以 W_n 都是哈密顿图.

（4）当 r=s\geqslant 2 时，K_{r,s} 为哈密顿图.

6.41 （1）所有的有向圈图 C_n(n\geqslant 3) 既是有向欧拉图，又是有向哈密顿图，图 6.37(a)所示为一个特例.

（2）让两个有向圈图 C_n(n\geqslant 3) 与 C_m(m\geqslant 3) 共一个顶点 v，所得图是有向欧拉图，但不是哈密顿图. 图 6.37(b)所示的图为一个特例.

（3）在一个有向圈图 C_n(n\geqslant 4) 的不相邻的顶点之间加一条有向边，所得图依然是哈密顿图，但不是欧拉图. 图 6.37(c)所示为一个特例.

（4）在（2）中所得图中的一个有向圈的不相邻顶点之间加一条有向边，所得图既不是欧拉图，也不是哈密顿图. 图 6.37(d)所示为一个特例.

图 6.37

6.42 利用主教材中定理 6.10 的推论（有割点的图一定不是哈密顿图）以及题 6.26 的结论证明本题.

设 G 为带桥（割边）e 的连通无向图. 若 G 是含 e 的 K_2，G 当然不是哈密顿图，否则，G 的阶数 n\geqslant 3，设桥 e=(u,v)，则由于 G 的连通性，u 与 v 中至少有一个不是悬挂顶点，不妨设 u 不是悬挂顶点，由题 6.26 可知，u 是割点，由主教材中定理 6.10 的推论可知，G 不是哈密顿图.

6.43 证明中用欧拉图的性质及握手定理的推论，使用归谬法.

若存在带桥的连通的无向图 G 是欧拉图，则 G 中所有顶点的度数都是偶数. 设桥 e=(u,v)，考虑 G'=G-e，由于 e 为桥，所以 G' 有两个连通分支 G_1' 与 G_2'，设 u 在 G_1' 中，v 在 G_2' 中，则 d_{G_1'}(u)=d_G(u)-1 为奇数，d_{G_2'}(v)=d_G(v)-1 为奇数，而 G_1' 与 G_2' 中其余顶点都是偶度顶点，这与握手定理的推论相矛盾.

6.44 根据无向欧拉图的判别定理，在图 6.9 中，图(a)没有奇度顶点，有欧拉回路. 图(b)中有 4 个（b,d,f,h）奇度顶点，没有欧拉通路，更没有欧拉回路. 图(c)中有 2 个（b,f）奇度顶点，有欧拉通路，但没有欧拉回路.

6.45 根据有向欧拉图的判别定理，在图 6.10 中，图(a)中顶点 b 的出度比入度大 1，顶点 d 的入度比出度大 1，另外 2 个顶点（a,c）的出度等于入度，故有欧拉通路，但无欧拉回路. 图(b)中 4 个顶点的出度都等于入度，故有欧拉回路. 图(c)中顶点 b 的入度比出度大 2，顶点 d 的出度比入度大 2，故没有欧拉通路，更没有欧拉回路.

6.46 在图 6.11 中，图(a)有桥，故没有哈密顿回路. 但它有哈密顿通路，如 fgeabcd. 对于图(b)，删去 \{b,d,f,h\} 后的图有 5 个连通分支，故没有哈密顿回路. 它也有哈密顿通路，如 abcdefghlijk. 图(c)有哈密顿回路，如 abcdhgfea. 图(d) 删去 \{b,d,f,h\} 后的图有 5 个连通分支，故没有哈密顿回路. 但它有哈密顿通路，如 abcdefghi.

6.47 （1）证明图 6.12(a)所示图 G 不是哈密顿图. 将此图顶点标定，见图 6.38(a)所示. 取 V_1=\{a,e,f,g,k\}，G-V_1 为图 6.38(b)所示，p(G-V_1)=6>|V_1|=5，由主教材中

定理 6.10 可知，G 不是哈密顿图.

图 6.38

（2）图 6.12(b)所示的图是哈密顿图. 将该图顶点标定，见图 6.39 所示. 在图 6.39 中，ahgfibcdeja 为图中一条哈密顿回路，所以该图为哈密顿图.

图 6.39

6.48 该青年应该按图 6.13 中所示带权图（各边均带有实数的图），走一条距离最近的哈密顿回路. 这里可用穷举法来寻找距离最近的哈密顿回路. 设：

这里，w(C_i) 为 C_i 的长度. 该青年按 C_1 或 C_6 中景点的顺序去旅游所走路程最近.

本题是在完全带权图 K_4 中求最短哈密顿回路问题，也称“货郎担问题”. 当 n 较大时，求解货郎担问题不是易事，计算量大得惊人.

6.49 本题是将有关事物之间的关系转化成无向图，证明所得图为哈密顿图的问题.

作无向简单图 G=\langle V,E\rangle，其中，V=\{v\mid v 为六种颜色的纱之一\}，则 |V|=6；E=\{(u,v)\mid u,v\in V 且 u\neq v 且 u 与 v 能搭配\}.

由已知条件可知，\forall u,v\in V，都有

由主教材中定理 6.11 可知 G 为哈密顿图，因而存在哈密顿回路，设 C=v_{i_1}v_{i_2}\cdots v_{i_6}v_{i_1} 为其中的一条，由 G 的构造可知，C 上任何两个顶点相邻当且仅当它们代表的颜色的纱能织成双色布. 比如，让颜色 v_{i_1} 与 v_{i_2} 染成的纱织成一种双色布，v_{i_3} 与 v_{i_4} 染成的纱织成另一种双色布，再让 v_{i_5} 与 v_{i_6} 染成的纱织成第三种双色布，三种双色布用上了 6 种不同颜色的纱.

6.50 图 6.14 所示平面图 G 的边数 m=14.

注意 桥在计算它所在的面的次数时都提供 2.

6.51 将图 6.15 所示平面图的内部面 R_1 变成外部面所得平面图如图 6.40(a)所示. 将 R_2 变成外部面如图 6.40(b)所示.

6.52 图 6.16 所示无向图 G 有平面嵌入，见图 6.41 所示，因而 G 为平面图.

根据“定理：设 G 为 n(n\geqslant 3) 阶平面图，则 G 为极大平面图当且仅当 G 的每个面的次数都是 3”，从图 6.41 可知，G 的 8 个面的次数均为 3，所以 G 为极大平面图.

图 6.40

图 6.41

6.53 图 6.42 中给出了两个 7 阶极小非平面图，其中图 6.42(a)所示的图为在 K_5 中插入两个 2 度顶点得到，图 6.42(b)所示的图为在 K_{3,3} 中插入一个 2 度顶点得到.

图 6.42

分析 若一个无向图 G 是平面图，则在 G 中插入有限个 2 度顶点，或消去有限个 2 度顶点（若存在 2 度顶点）后所得图 G' 仍然是平面图. 同样地，对一个非平面图 G 进行插入 2 度顶点，或消去 2 度顶点（若存在），所得图 G' 仍为非平面图. 也就是说，2 度顶点的多少不影响图的平面性. 已知 K_5 和 K_{3,3} 都是极小非平面图，则与它们同胚的图也是极小非平面图. 图 6.42(a)所示的图与 K_5 同胚，所以它是 7 阶极小非平面图，删除它中的任何一条边后所得图为平面图. 类似讨论可知图 6.42(b)所示的图也是 7 阶极小非平面图.

6.54 G 的边数 m=11.

分析 由于 G 是连通的平面图，所以 G 的阶数 n、边数 m、面数 r 满足欧拉公式：

已知，n=7，r=6，所以 m=n+r-2=7+6-2=11.

6.55 G 的阶数 n=9.

分析 由于 G 的连通分支数 k=3，应用欧拉公式的推论应有

已知，r=4，m=9，所以阶数 n=k+1+m-r=3+1+9-4=9.

6.56 （1）证明图 6.17(a)所示图为非平面图. 图 6.43 所示的图为图 6.17(a)所示图的子图. 此图与 K_{3,3} 同构，互补顶点子集 V_1=\{a,b,c\}，V_2=\{1,2,3\}，由库拉图斯基定理可知，图 6.17(a)所示的图为非平面图.

（2）图 6.17(b)所示的图是 5 阶简单图，且图中任何两个顶点均彼此相邻，所以该图与 K_5 同构，由库拉图斯基定理可知，该图为非平面图.

图 6.43

6.57 论证图 6.18 所示的图有平面嵌入. 设此图为 G，将 G 的各顶点标定，见图 6.44(a)所示. 只要将顶点 b（或顶点 a）移动位置，就可得到 G 的平面嵌入，见图 6.44(b)所示，所以 G 为平面图.

图 6.44

分析 证明某图 G 为平面图，只要找出 G 的平面嵌入即可. 而证明某图 G 为非平面图，就要找到与 K_5 或 K_{3,3} 同胚子图，或者找到可以收缩到 K_5 或 K_{3,3} 的子图，由库拉图斯基定理可证明 G 为非平面图.

6.58 在图 6.45 中，虚心点实线边所示的图为轮图 W_5，而实心点虚线边所示的图为 W_5 的对偶图 W_5^{*}，W_5^{*} 也是 5 阶轮图，只是它的外部面由次数为 3 的面充当，因而在同构的意义下，它们都是 5 阶轮图，所以 W_5^{*}\cong W_5.

图 6.45

6.59 由主教材中定理 6.13 和欧拉公式证明本题.

由于 G 是连通平面图，因而满足欧拉公式：

又由于 G 的每个面的次数至少为 4，及主教材中定理 6.13 可知

由②可得

将③代入①，可得

解读：点着色的实际含义是「相邻的顶点必须分开」。凡是把冲突关系画成图的问题（排考试、分频率、定时间），最少颜色数就是所需的最少时段数。

6.60 （1）C_7 至少要用 3 种颜色. （2）C_8 至少要用 2 种颜色. （3）W_9 至少要用 3 种颜色. （4）W_{10} 至少要用 4 种颜色. （5）K_n 至少要用 n 种颜色. （6）K_{r,s}，当 s\geqslant 1 且 t\geqslant 1 时至少要用 2 种颜色；当 s=0 或 t=0 时只需要一种颜色.

分析 偶阶圈图至少要用 2 种颜色，奇阶圈图至少要用 3 种颜色. 偶阶轮图至少要用 4 种颜色，奇阶轮图至少要用 3 种颜色. n 阶完全图要用 n 种颜色. 二部图只要 2 种颜色，当二部图为零图时只要一种颜色.

6.61 图 6.11(a)、(b)、(c)、(d)分别至少要用 3、3、2、3 种颜色.

6.62 做无向图 G=\langle V,E\rangle，V=\{v_i\mid i=1,2,3,4,5\}，E=\{(v_i,v_j)\mid v_i 与 v_j 有人同时选，1\leqslant i<j\leqslant 5\}，如图 6.46 所示. 显然，课程 v_i 与 v_j 可以同时考当且仅当没有人同时选 v_i 与 v_j，又当且仅当在 G 的着色中 v_i 与 v_j 可涂同一种颜色. 不难看出给 G 着色至少需要 3 种颜色，给 v_2 与 v_5 涂颜色 \alpha，v_1 与 v_4 涂颜色 \beta，v_3 涂颜色 \gamma. 因而至少需要 3 个时间段才考完这 5 门课程.

6.63 作图 G=\langle V,E\rangle，V=\{v_i\mid i=1,2,3,4,5,6\}，每个 v_i 代表一台设备，E=\{(v_i,v_j)\mid v_i 与 v_j 的距离小于 200 公里，1\leqslant i<j\leqslant 6\}，如图 6.47 所示. 给顶点着色，一种颜色代表一个频率. 一种着色代表一种频率分配方案，因而所需的最少频率数等于 G 需要的最少颜色数. 不难看出，G 最少需要 3 种颜色. 图 6.47 中给出一种着色方案. 按照这个方案，设备 1 和 3 使用频率 1，设备 4 和 5 使用频率 2，设备 2 和 6 使用频率 3.

6.64 做图 G=\langle V,E\rangle，其中 V=\{v_i\mid i=1,2,3,4,5,6\}，每个 v_i 代表一名博士，E=\{(v_i,v_j)\mid A_i\cap A_j\neq\varnothing,1\leqslant i,j\leqslant 6,i\neq j\}，如图 6.48 所示. v_i 与 v_j 的答辩会可以同时进行当且仅当 A_i 与 A_j 中没有共同的成员，这又当且仅当 v_i 与 v_j 不相邻. 因而，这个问题恰好对应 G 的顶点着色，着不同颜色的顶点所代表的博士生的答辩必须安排在不同时间，需要的最少不同时间等于 G 需要的最少颜色数. 不难看出，G 需要的最少颜色数是 5，只有 v_4 和 v_5 可以着同一种颜色. 因此，这次论文答辩至少要安排 5 个不同的时间，其中 A_4 和 A_5 可以安排在同一时间.

图 6.46

图 6.47

图 6.48