第9章 习题解答
22得2≤m－m＋m，化简后得m≥30，矛盾。
35因而G中存在次数小于等于4的面。
6.用Kuratowski定理1和Kuratowski定理2证明图9.74两个图是非平面图。
解：图9.99所示的图是图9.74(a)的子图，它与K3.3在2度结点内同构，由定理9.8.12(Kuratowski定理1)知图9.74(a)是非平面图。
图9.100所示的图是图9.74(b)的子图，它可以收缩到K3.3，由定理9.8.13(Kuratowski定理2)知图9.74(b)是非平面图。
7.画出图9.75中各图的对偶图。
31
第9章 习题解答
解：图9.75(a)的对偶图如如图9.101所示。 图9.75(b)的对偶图如图9.102所示。 图9.75(c)的对偶图如图9.103所示。
8.对图9.75中各图的面进行着色，求出它们的着色数X *(G)。
32
第9章 习题解答
解：将图9.75改画为图9.104。 ⑴对图9.104(a)的面进行着色： ①面efghe和外部面abcda着红色。 ②面abfea和面cdhgc着蓝色。 ③面aehda和面bcgfb着绿色。 该图的着色数X *(G)=3。
⑵对图9.104(b)的面进行着色： ①外部面abcdefa着红色。 ②abga，cdgc和efge着蓝色。 ③bcgb，degd和agfa着绿色。 该图的着色数X *(G)=3。
⑶对图9.104(c)的面进行着色： ①外部面abcbda着红色。 ②内部面abda着蓝色。 该图的着色数X *(G)=2。
9.用韦尔奇?鲍威尔法对图9.76着色。
解：①按照度数递减次排列各结点：c,g,d,e,f,h,a,b，它们的度数分别是5，5，4，4，4，4，3，3。
②用第一种颜色对c着色，并对与c不相邻的结点f也着上同样的颜色。 ③用第二种颜色对剩下的结点g,d着色。
33
第9章 习题解答
④用第三种颜色对e, a着色。 ⑤用第四种颜色对h,b着色。
10.设G=?V,E?是自对偶图，|V|=n，|E|=m，证明：2(n–1)=m。
证明：设G的面数为r，图G的对偶图G*的结点数，边数和面数分别为n*, m*和r*。 由对偶图的定义可知m=m*，n=r*，r=n*。
因为G是自对偶图，G与G*同构，故n=n*，所以n=n*=r。，将n=r代入欧拉公式n－m＋r=2得m=2(n–1)。
11.设图G是简单平面图，如果G是自对偶图，证明G中至少存在4个3度点。 证明：设n，m，r分别为G的结点数，边数和面数，vi是G的任一结点，ri*是G*的对应于结点vi一个面，deg(vi)=deg(ri*)。因为G是简单图且G与G*同构，deg(vi)=deg(ri*)≥3所以，当deg(vi)=3时，3n=2m，m=1.5n。代入公式2(n–1)=m=1.5n，解之，n=4, 所以，自对偶图至少有4个3度结点。
12.证明：平面图G的对偶图G*是欧拉图当且仅当G中每个面的次数均为偶数。 证明：? G*是欧拉图，G*的每个结点是偶度的，再由定理9.8.14(4)知，G的每个面的次数为偶数。
?G的每个面的次数为偶数，由定理9.8.14(4)知G*的每个结点度数为偶数，G*是欧拉图。
13.证明一个无向图能被两种颜色正常着色当且仅当它不包含长度为奇数的回路。 证明：?设图G=?V,E?是一个不包含长度为奇数的回路的连通图。下证，G能被两种颜色正常着色。
?u?V，构造V的两个子集：V1=? v|从u到v有一条偶数长度的基本路? V2=? v|从u到v有一条奇数长度的基本路?
显然V=V1∪V2，可以证明V1∩V2=?，反证法，?v?V1∩V2，则u到v有一条偶数长度的基本路，也有一条奇数长度的基本路，这两条基本路合起来，G中必有一条奇数长度的回路，矛盾。因此V1和V2构成了的一个划分。
以下证明，V1(V2)中任两个结点不相邻。
反证法，如果V1(V2)中有两个结点v1, v2相邻，则u到v1有偶(奇)数长度的基本路，u到v2有偶(奇)数长度基本路与(v1, v2)合起来构成一条长度为奇数的回路，这是不可能的。这样，图G中每条边所关联的两个结点一个在V1中，另一个在V2中。将V1中的结点着上一种颜色，将V2中的结点着上另一种颜色，就得到了G的一种正常着色。
?设G能被两种颜色正常着色，下证G中不包含长度为奇数的回路。 如果G是不连通的，只要对G的每个连通分支证明就可以了。 令V1=? u| u?V，u着上第一种颜色?， V2=? u| u?V，u着上第二种颜色?， 对于G中任一长度为k的回路C：v0v1v2…vk-1v0，由于相邻结点颜色不同，如果v0?V1，v1?V2,，v2?V1，… vk-1?V2,，v0?V1，故k-1一定是奇数，k是偶数，C是长度为偶数的回路。
所以G中不含长度为奇数的回路。 34