例。设图G 中度序列满足：d1 ? ??? d? ，则 ? ? maxmin{di?1,i} 。
i证明：不妨设顶点排序 ?：v1，??，v? 恰使d(vi ) = d i i=1,2,...,? 。沿? 进行贪心着色。
设vk被着上了色? 。易见，它一定与前面 ? ? -1个不同色的顶点相邻，因此
dk＝ d(vk) ? ? - 1 。 又，显然
ｋ? ? 。 ∴ min {dk + 1，k} ? ? 得证。 #
例。试证：?(G) ? 1+ max{ ?(H) | H为G的导出子图}。 证明：作G的顶点排序 ?：v1，??，v? 如下： v? 为图G的最小度顶点； v?-1 为图G-v? 的最小度顶点； v??? 为图G-{v?，v?-1} 的最小度顶点； ??????
令L = max{ ?(H) | H为G的导出子图}。注意到G，G-v? ，G-{v?，v?-1} ，?都是G 的导出子图。从而，每个dH(vi) ? L，于是每个vi 都只与前面? L个顶点相邻。因此贪心着色法至多用了L+1个色。故
?(G) ? 1+L = 1+ max{ ?(H) | H为G的导出子图} 。 #
注 顶点着色问题的另一常用技巧是基于以下显而易见的命题： 设d(u) ? k-2 (k ? 2) ? u ? U ? V，而G-U为k-可着色的，则G也是k-可着色的。 例。试证 ?(G)+?(Gc) = ? +1。
证明：对? 进行归纳。当? ? 2时，显然成立。假设对顶点数< ? 时都成立，而?(G)=? 。 情况1 当?(G)? ?(G)-1时：则
c
?(G)= ?-1-?(G)? ? - ?(G) 。
cc
?(G) ? ?(G)+ 1? ? -?(G)+1，得证。 情况2 当?(G) < ?(G)-1时：取u使
dG(u) = ?(G) ? ?(G) -2 。 因此，首先有
?(G1) = ?(G) 。 其中G1=G - u 。由归纳假设知，
?(G1) + ?(G1c) = ?。
∴ ?(G)+?(Gc) = ?(G1)+?(Gc) ? ?(G1)+?(G1c) +1 = ? +1。 #
习题
8.1.1. 证明：若C =（E1，E2，??，E? ）是图G的一个?-着色，则任二Ei与Ej间至少有一边相连。
8.1.2. 证明：若G的任二奇圈都有公共顶点，则? ? 5 。
8.1.3. 证明： 设图G 中度序列满足：d1 ? ??? d? ，则 ? ? maxmin{di?1,i} 。
i
8.1.4. 利用习题8.1.3 证明：
(a) ? ?
(b) ?(G)+?(Gc) = ? +1。 (c) 推论8.1.1 。
8.1.5. 试证：?(G) ? 1+ max{ ?(H) | H为G的导出子图}。 8.1.6.* 设k-色图G上有这样一个正常着色（不一定为k-着色），其中每种色都至少分配给两个顶点。证明：G也有这样的k-着色 。
8.1.7. 证明：若G 是简单图，则 ? ? ?2/(?2 - 2? ) .
8.1.8. 若G 的任二k-着色都导出V的相同的k-划分，则称G为唯一k-可着色的。 8.1.9. 证明：k-临界图没有顶点割能导出唯一(k-1)-可着色子图。
8.1.10, (a) 证明：若u，v为临界图的二顶点，则不可能有N(u) ?N(。 (b) 试证：不存在恰有k+1个顶点的k-临界图。
8.1.11. (a) ?(G1?G2) = ?(G1) +?(G2) ，其中G1?G2 称为图G1与G2的联图，它是将
36
?2?? 。
它们间的每对顶点都用新边连起来所得的图。 (b) G1?G2是临界图，当且仅当G1与G2都是临界图。
8.1.12. 设G1与G2是恰有一公共顶点v的k-临界图，且vx和vy 分别是G1和G2的边， 则 (G1-vx)?(G2-vy)+xy也是k-临界图。
8.1.13. 对 n = 4及 n ? 6 构造n个顶点的4-临界图。
8.1.14.* (a) 设V的2-划分（X，Y）使G[X]和G[Y]都是n-可着色的，且边 割 [X，Y] 最多有n-1条边，则G也是n-可着色的。 (b) 试证：每个k-临界图都是(k-1)-连通的。
Brooks 定理
定理8.4 设简单连通图G既为非奇圈、亦为非完全图，则? ? ? 。
证明：对? 进行归纳。当? ? 3时，显然成立。假设当? < n时都成立，而?(G) = n。不妨设：① G为?-正则的。（不然，取u使d(u)= ? < ? ，由归纳假设，易见，G - u为 ? -可着色的，从而G亦然。） ② G为2-连通的。（不然，令v为G的割点，则存在E的2-划分（E1，E2）使G[E1]与G[E2]恰有一公共顶点v，从而易见，结论成立。）③ ? ? 3。（不然，G为圈，结论成立。） 今选取3个点 x1 ，x2，xn 如下：
若 ? ? 3，则任取一点为xn ，并取N(xn）中任二不相邻顶点作为 x1 与x2 。（ 这样的二顶点一定存在。不然，N(xn）? {xn} 是一团，从而G是完全图，矛盾。）
若 ? = 2，则选取xn使 ?(G - xn )= 1。注意到G - xn中至少有2个endklocks （即，只含G的一个割点的G的块），每个至少含一G的非割点与xn 相邻接。取不在同一endklock中的两个这种顶点作为x1 与x2 。
在上述两种情况下，我们都有 G - {x1, x2} 连通； 且 xnx1 ， xnx1 ? E(G) 而x1x2 ? E(G) 。 下面我们来作V的一个排序： 取xn-1 ? V \\{x1, x2, xn}; 取xn-2 ? V \\{x1, x2, xn-1, }; .................................
由于G - {x1， x2}之连通性，上述步骤可一直进行到底。得V的一个排序：
x1， x2，??，xn 。
其中每个xi （i < n )都至少与某xj ，j > i，相邻接。又，x1 与x2不相邻。于是，贪心着色法只用了? ? 个色。 #
习题
8.2.1. 证明Brooks定理等价于下述命题：若G是k-临界图（k ? 4），且不是完全图，则2? ? ?(k-1)+1 。 8.2.2. 利用Brooks定理证明：若G是? = 3的无环图，则?? ? 4。
围长和色数
易见，若G中最大团的顶点数k，则? ? k。下面的定理表明，一个有很大色数的图，其最大团的顶点数不一定也很大。
定理8.7 对任正整数k，都存在不含K3的图G使 ?(G) = k 。 (即，可找到色数任意大的图，但其最大团顶点数却只为2。）
证明：对k进行归纳。当k = 1时，G1 = K1满足要求；当k = 2时，G2 = K2 也满足要求；一般，设
37
Gk = (Vk , Ek ) ，Vk = {v1，??，vn）满足要求（k ? 2） ，则构造 Gk+1 = (Vk +1, Ek+1 )如下：令
Vk+1 = Vk ? {u1，??，un}? {v}。
其中 u1，??，un，v 为新加的顶点。将每个u i 与N(vi)中每个顶点用新边连起来；再将u与每个ui 也都新边连起来，所得图即为Gk+1 。
易见，Gk+1中不含K3。又，Gk的任一k-着色可扩充成Gk+1的（k+1）-着色如下：将每个ui着以vi
上的色；再用一新色着在v上。显然，这是Gk+1的正常（k+1）-着色，从而Gk+1是（k+1）-可着色的。余下只要再证Gk+1不是k-可着色的即可：不然，不妨设在该k-着色中v被着以色k。这时无一ui被着以色k。今，将每个被着以色k的顶点vi都改着以顶点ui的色。易见，这是Gk+1的正常k-着色。它导致Gk的一个正常（k-1）-着色，这与Gk为k色图相矛盾。 #
注 Hajos曾提出似乎是可信的猜想： G为k-色图 ? G包含Kk的一个剖分。 当k=3及4时可证猜想成立。但1986年已证明该猜想不成立。
习题
8.3.1. 证明：定理8.7中的图Gk是一k-临界图。
?k??8.3.2(a) 设G是围长至少为6的k-色图（k ? 2）。作一新图H如下：取k?个新顶点集S及G的??
???*
个互不相交的拷贝，且建立G的拷贝与S的?个顶点的一一对应。再将G的每个拷贝与它在S中相对应的?个顶点之间用一匹配连接起来。证明：H的色数至少为k+1，其围长至少6。
(b) 试证：对任k ? 2，都存在围长为6的k-色图。
平面图 平图和平面图
图G可嵌入（embededable）于平面中 ? G可画在平面上，使它的边只在端点处才可能相交叉。 （该画法称为G的一个平面嵌入（planar embedding）或平图 （plane graph））
? G为平面图（planar graph）
例。K5，K3,3 以及它们的剖分都是非平面图。它们中任一个去掉任一边后都是平面图。 注意 平面图和平图间的区别。后者是前者的一个几何实现（具体画法）。
Jordan 曲线定理 平面中任一Jordan 曲线J（连续不自交的闭曲线），将余下的平面划分成二不相交开集：J的内部（interior）和 J的外部（exterior），分别记为 int J和ext J。（它们的闭包分别记为Int J 和 Ext J）。连接int J中一点到ext J中一点的任一条曲线一定与J交于某一点。
定理9.1 K5为非平面图。
证明：反证，假设G为K5的一个平图。令G的五个顶点为v1，??，v5。注意到圈
C = v1v2v3v1 为平面上的一条Jordan 曲线，且v4必在int C 或ext C中。若v4 ? int C，则边v4v1， v4v2，与v4v3将int C划分成三个区域int C1，int C2，和int C3。
这时v5一定在上述三个区域及区域ext C之一。若v5 ? ext C，则因v4 ? int C，边v4v5 必与C交于某一点，这与G为平面图的假设相矛盾。其它情形类似地也导致矛盾。 #
定理9.2.’ K3,3为非平面图。
38
证明：类似，略。
平面嵌入的慨念可推广到其它平面上。称 图G可嵌入于曲面S上 ? G可画在S上，使它的边仅在端点处才可能相交叉。 例。K5和K3,3都可嵌入于环面上； K3,3可嵌入于Mobius带上；每个图都可“嵌入”于三维空间3
R中。
定理9.2 G可嵌入于平面上 ? G可嵌入于球面上。 证明：利用球极平面射影，略。 #
对偶图
平图G的面（face） ? G将平面划分出来的连通区域的闭包。 外部面（exterior face） ? G中唯一的无界面。
定理9.3. 对平面图G 的任一顶点，都存在G的一个平面嵌入，使它在该嵌入的外部面上。 证明： 先将G嵌入于球面上，并将球面的北极放在含该顶点的G的一个面中，再利用球极平面射影。 #
v1记号 F(G) = 平图G的面的集合。 f5e6 ?(G) = 平图G的面数。 v7e1f3e7ee4 b(f) = 面f的周界。
9当G连通时，b(f)可当作一闭途径，其中G在b(f)f4v2f1v6eev4中的每一割边在该途径中都恰被走过两次。当G为2-58连通时，b(f) 为一圈。 f2e2e3例。 b(f1) =
v3v1e1v2e5v4e8v6e9v6e8v4e4v1e6v7e7v7e6v1 。
b(f5) = v1e1v2e2v3e3v4e4v1 。
在平图G中面f与它的周界上的边和顶点相关联。称G的一边e分隔（seperate）与它相关联的面。易见，
e为G的割边 ? e只与G的一个面相关联 ? e恰分隔G的一个面。 e为G的非割边 ? e恰与G的两个面相关联 ? e恰分隔G的两个面。 平图G中面f的度（degree）
dG(f) = 与面f 相关联的边数（割边记为2）。 例如，d(f1) = 9。
平图G的对偶图（dual graph）G*是这样的一个图：它们之间有如下的一一对应关系
e4e3 G的面f ? G*的顶点f* ；
e1 G的边e ? G*的边e* 。 e2fe5f1且 f2e84** * * f3 G的顶点f1与f2被边e连接
e7f5e6 ? G的面f1与f2 被边e
分隔。
* **
例如，左面所示平图G的对偶图G= (V , E) 为
V* = {f1*，??，f5*} ， E* = {e1* = f1*f5* ， e2* =f5*f5* ，e3* = f2*f5* ，??，e8* = f2*f3*} 。
39
易见，平图G的对偶图G*是一平面图，事实上存在G* 的一个平面嵌入（称为几何对偶）e4e3*
如下：在G的每个面f中放置顶点f，对应于G
e1e2的每一边e，画一条边e* 使它穿过e恰好一次（且f1e8e5ff24不穿过G的其它边）。例如，上例平图G的对偶f3e7图G* 如右图所示。 f5e6*
由上述知，G 一定是连通平面图。且有 e是G的环 ? e* 是G* 的割边。
e是G的割边? e* 是G* 的环。
*
有时，为方便计，把平图G的几何对偶G当作G的对偶图。这时，若G连通，则有 G** = (G* )* ? G。 （当G不连通时，上式不一定成立）。
*
注意 “平图G ? H ? G ? H* ”不一定成立。
例如，右边二平图是同构的，但它们的对偶图并不同构。因此，对偶图的概念只对平图有意义，不能推广到平面图上。
由G* 的定义易知： ?(G* ) = ?(G)
*
?(G) = ?(G)
dG*f???d?f? ?f?F?G?
*G
定理9.4 设G为平图，则
?d(f)?2?
f?F
证明：左式?G***f?V(G)?d(f*)?2?(G*)?2?(G) 。 #
习题
9.2.1 .(a)证明：图G是平面图 ? G的每个块都是平面图。 (b)试证：极小非平面图是简单块。
9.2.2. 若一平图和它的对偶图同构，则称该平图为自对偶的。 (a) 若G为自对偶的，则? = 2? - 2 。 (b) 对每个 n ? 4 ，找出n顶点的自对偶平图 。
9.2.3. (a) 证明：B是平图G的键 ? { e* ? E(G* ) | e ? B } 是G* 的圈。 (b) 证明：C是平图G的圈 ? { e* ? E(G* ) | e ? C } 是G* 的键。 (c) 试证：Euler平图的对偶图是偶图。 9.2.4. 设G是平图，证明： (a) (G* )* ? G ? G是连通图。 (b) ?(G** ) = ?(G) 。
9.2.5. 设T是连通平图G的生成树，E* = {e?E(G)e?E(T)}。证明：T* = G*[E*] 是G* 的
**生成树。
9.2.6. 每个面的度都是3的平图称为平面三角剖分图。证明：每个? ? 3的简单平图都是某简单平面三角剖分图的生成子图。
9.2.7. 设G是? ? 4的简单平面三角剖分图，证明：G*是简单2-边连通3-正则平面图。 9.2.8.* 证明：任何平面三角剖分图，都包含一个有2? (G)/3条边的偶子图。
Euler 公式
定理9.5 (Euler) 设G为连通平图，则 ? - ? + ? = 2 。
40