届时请关注本版置顶的：
北大版《离散数学教程》习题解答（含“教材定理汇总”和“北大历年考研离散真题解答”）
（http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=29548）

同时欢迎版友继续提出修订建议（尤其是对解答的疑问、各类错误的报告等），谢谢！
^_^

以下是楼主的解答：

(1) 2 种。
证明: 首先，由于1-色图只有零图，而零图是平面图，所以给极小非平面图着色至少需要2 种颜
色。另一方面，由于K3,3 是极小非平面图，且χ(K3,3) = 2，从而极小非平面图点色数的最小值
为2。2

(2) 5 种。
证明: 设G 是n 阶极小非平面图， e ∈ E(G) 是G 中任意一条边。令H = G - e，则H 是
平面图。由教材定理11.10 可知，|E(H)| <= 3n - 6。从而|E(G)| = |E(H)| + 1 <= 3n - 5。即
∑ d(vi)(vi ∈ V (G)) = 2|E(G)| <= 6n - 10。由鸽巢原理可知，G 中存在度数小于等于5 的顶点v。易见，
G - v 是平面图，从而由Heawood 定理可知，G - v 是5-可着色的。仿照Heawood 定理证明中的
换色方法可知，G 也是5-可着色的。这就是说，极小非平面图的点色数不超过5。
另一方面，由于K5 是极小非平面图，且χ(K5) = 5，所以极小非平面图点色数的最大值即
为5。

在(2)的解答中，对“由鸽巢原理可知，G 中存在度数小于等于5 的顶点v。”这一步推理不是很理解，希望能详述一下，谢谢了！

2)最多需要 5 种颜色。

极小非平面图去掉1条边就是平面图，根据四色定理，它可以4着色。加入原来的那条边，至多会引起2个顶点的冲突，至多再增加1种颜色就会解决冲突，所以至多需要5种颜色。极小平面图k5恰好需要5种颜色。