离散数学作业-20251123-第九章(2)
离散数学作业 20251123 第九章-2
9.7
设连通平面图 $G$ 的顶点度数至少为 3，且其面数 $f < 12$，证明 $G$ 有一个面的边数小于 5。
证明：
假设对任意一个面，有 $deg®\ge 5$，由 $\sum deg®=2|E|$，知 $f \le \dfrac{2}{5}|E|$.
由于 $G$ 的顶点度数 $\delta(G) \ge 3$，由 $\sum \deg(v) = 2|E|$ ，知： $2|E| \ge 3|V| \implies |V| \le \dfrac{2}{3}|E|$。
由欧拉公式：$v-e+f=2$，得 $$\dfrac{2}{3}|E| - |E| + \dfrac{2}{5}|E| \ge 2$$.
故 $$|E| \ge 30$$.
所以 $e-\dfrac{2}{3}e+f\ge v+f-e=2$ 得 $e\le 3f-6$.
故 $\dfrac{5}{2}f\le e\le 3f-6$ 得 $f\ge12$ 矛盾！
9.8
设图 $G$ 的顶点度数至少为 3，且其面数 $f < 12$，则 $G$ 是 4-面可着色的。
证明：
设 $G^$ 为 $G$ 的对偶图（Dual Graph）。$G$ 的面着色问题等价于 $G^$ 的顶点着色问题。
由于 $G$ 是平面图，故其对偶图 $G^$ 亦为平面图，且 $G^$ 的顶点数 $|V(G^*)| = f$。
由 9.7 的结论可知，平面图 $G^*$ 中必然存在度数 $\deg(v) \le 4$ 的顶点。
由四色定理，任意平面图 $G^$ 的顶点色数 $\chi(G^) \le 4$。
即 $G^*$ 是 4-顶点可着色的。
故原图 $G$ 是 4-面可着色的。
9.9
若将平面分为 $f$ 个面，每两个面都相邻，问 $f$ 最大为多少？
证明：
设该平面划分对应的平面图为 $G$，其对偶图为 $G^*$。
由于 $G$ 中每两个面都相邻，则 $G^*$ 中代表面的 $f$ 个顶点两两相邻。
故 $G^*$ 为 $f$ 个顶点的完全图 $K_f$。
因为 $G$ 是平面图，故 $K_f$ 也必须是平面图。
对于简单连通平面图，若 $|V| \ge 3$，需满足 $|E| \le 3|V| - 6$。
在完全图 $K_f$ 中，$|V|=f$，$|E|=\dfrac{f(f-1)}{2}$。
代入得：$$\dfrac{f(f-1)}{2} \le 3f - 6$$
解得 $3 \le f \le 4$。
且当 $f=5$ 时，$K_5$ 的边数 $|E|=10$，而 $3|V|-6 = 3(5)-6=9$，因 $10 > 9$，故 $K_5$ 非平面图。
故 $f$ 最大为 4。
以下是题目文本的 Markdown 以及符合严谨数学风格的证明过程。
9.14
证明：若图 $G$ 中任意两个奇回路均有一个公共顶点，则 $\chi(G) \le 5$。
证明：
若 $G$ 中不存在奇回路，则 $G$ 为二部图，$\chi(G) \le 2 < 5$，命题成立。
若 $G$ 中存在奇回路，设 $C$ 为 $G$ 中的一个奇回路，顶点集为 $V©$，且 $\chi© = 3$。
考虑导出子图 $G’ = G - V©$。
假设 $G’$ 中存在奇回路 $C’$，则 $C’$ 亦为 $G$ 中的奇回路。
根据题目，任意两个奇回路均有一个公共顶点，所以 $V© \cap V(C’) \neq \emptyset$。
但 $G’$ 是移除了 $V©$ 后得到的图，故 $V(C’) \cap V© = \emptyset$，矛盾。
因此，$G’$ 中不包含任何奇回路，$G’$ 为二部图，即 $\chi(G’) \le 2$。
将 $G’$ 的着色方案与 $C$ 结合，可以有：
$\chi(G) \le \chi(G’) + \chi© = 2 + 3 = 5$。
证毕。
9.16
(1) 证明：由任意有限条直线（可以相交）划分平面所得的图是面两色的。
(2) 证明：由任意有限个圆（可以相交）划分平面所得的图是面两色的。
(1) 证明：
运用数学归纳法：
-
当 $n=1$ 时，平面被分为两个半平面，分别着色为黑、白，满足面两色，命题成立。
-
假设当 $n=k$ 时命题成立，即平面已被着色。
-
当 $n=k+1$ 时，设新加入的直线为 $L$。$L$ 将平面分为两个半平面 $H_1, H_2$。
保持 $H_1$ 中的原有着色不变，将 $H_2$ 中所有区域的颜色反转（黑变白，白变黑）。
对于不与 $L$ 相邻的边界，两侧颜色性质未变，依然满足条件。
对于 $L$ 上的边界，其两侧原本同色，因 $H_2$ 侧反转，现变为异色，满足相邻面颜色不同。
由数学归纳法，命题得证。
(2) 证明：
对圆的个数 $n$ 进行数学归纳。
-
当 $n=1$ 时，圆内着色黑，圆外着色白，满足面两色，命题成立。
-
假设当 $n=k$ 时命题成立。
-
当 $n=k+1$ 时，设新加入的圆为 $C$。保持圆 $C$ 外部的着色不变，将圆 $C$ 内部所有区域的颜色反转。
对于非 $C$ 的边界，两侧颜色性质未变，依然满足条件。
对于圆 $C$ 构成的边界，其两侧原本同色，现一侧反转，变为异色。
由数学归纳法，命题得证。
9.17
证明：
设完全二部图 $K_{m,n}$ 的两部分顶点集分别为 $X = {x_0, x_1, \dots, x_{m-1}}$ 和 $Y = {y_0, y_1, \dots, y_{n-1}}$。
不妨设 $m \le n$。此时 $\Delta(K_{m,n}) = \max(m, n) = n$。
显然 $\chi’(K_{m,n}) \ge \Delta(K_{m,n}) = n$。
构造如下边着色函数 $c: E \to {0, 1, \dots, n-1}$：
对于任意边 $e = x_i y_j$ （其中 $0 \le i < m, 0 \le j < n$），定义：
$$c(x_i y_j) = (i + j) \pmod n$$
验证：
-
考察顶点 $x_i$ ($i$ 固定)：
与其相连的边为 $x_i y_0, x_i y_1, \dots, x_i y_{n-1}$。
对应的颜色为 $(i+0), (i+1), \dots, (i+n-1) \pmod n$。
这构成了模 $n$ 的完全剩余系，即颜色互不相同。
-
考察顶点 $y_j$ ($j$ 固定)：
与其相连的边为 $x_0 y_j, x_1 y_j, \dots, x_{m-1} y_j$。
对应的颜色为 $(0+j), (1+j), \dots, (m-1+j) \pmod n$。
由于 $m \le n$，这些值在模 $n$ 意义下显然互不相同。
该构造使用了 $n$ 种颜色，且为正常边着色。
故 $\chi’(K_{m,n}) \le n$。
综上，$\chi’(K_{m,n}) = n = \Delta(K_{m,n})$。