电子科技大学-图论第三次作业-杨春7页

1、图论第三次作业第六章习题2.证明：根据欧拉公式的推论，有ml*(n-2)/(l-2),(1)若deg(f)4,则m4*(n-2)/2=2n-4;(2)若deg(f)5,则m5*(n-2)/3,即：3m5n-10;(3)若deg(f)6,则m6*(n-2)/4,即：2m3n-6.3.证明：G是简单连通图，根据欧拉公式推论，m3n-6;又，根据欧拉公式：n-m+=2,=2-n+m2-n+3n-6=2n-4.4.证明：(1)G是极大平面图，每个面的次数为3，由次数公式：2m=fdeg(f)=3,由欧拉公式：=2-n+m,23m=2-n+m,即：m=3n-6.(2)又m=n+-2,=2n-4.(3)对

2、于的极大可平面图的的每个顶点，有，即对任一一点或者子图，至少有三个邻点与之相连，要使这个点或子图与图G不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使，由点连通度的定义知。5.证明：假设图G不是极大可平面图，那么G不然至少还有两点之间可以添加一条边e，使G+e仍为可平面图，由于图G满足，那么对图G+e有，而平面图的必要条件为，两者矛盾，所以图G是极大可平面图。6.证明：(1)由知当n=5时，图G为，而为不可平面图，所以，（由和握手定理有，再由极大可平面图的性质，即可得）对于可平面图有，而，所以至少有6个点的度数不超过5.(2)由和握手定理有，再由极大可平面图的性质，即可得，对于可平

3、面图有，而，所以至少有12个点的度数不超过5.8.证明：(1)由握手定理和极大可平面图的性质，可得对恒成立，又，所以，即。(2)由定理5，对简单可平面图都有，又图G是的简单连通平面图，所以G中至少有3个点的度数小于等于5.(3)由定理5，对简单可平面图都有，又图G是的简单连通平面图，所以G中至少有4个点的度数小于等于5.17.证明：利用反证法，假设存在6连通可平面图，设G是6连通图，则：k(G)6由惠特尼定理可得：(G)k(G)6,m3n-6,这与G是简单平面图相矛盾，因此假设不成立，不存在6连通可平面图19.证明：假设不存在面f,使得deg(f)5,则：2m=fdeg(f)6,由欧拉公式得：

4、=2-n+mm3,于是得：2m3n-6,另一方面，由(G)3得：2m3n3n-6与上面得到结果相矛盾，所以假设不成立，G至少存在一个面f,使得：deg(f)5.第七章作业2.证明：设n=2k+1,G是正则单图，且0,m(G)=n2=(2k+1)2k,由定理5可知(G)=(G)+1.28.解：(1)又：=k(k-1)(k-2)2(k-3)+k(k-1)2(k-2)=k(k-1)(k-2)(k2-4k+5) =k(k-1)(k-2)2(k-3),所以，原图色多项式为：k(k-1)(k-2)2(k2-4k+5)-k(k-1)(k-2)2(k-3) =k(k-1)(k-2)2(k2-5k+8)(2)原

5、图与该图同构，又，同构的图具有相同的色多项式，所以原图色多项式为：k(k-1)(k-2)2(k2-5k+8)。31.证明：(1)用归纳法来证明。当m=1时，直接计算Pk(G)=km-km-1,得km-1系数为-1，且Pk(G)中具有非零系数的k的最小次数为1即G分支数，故m=1时命题成立；设对于少于m条边的一切n阶单图命题均成立，考虑单图G=(n,m),由递推公式：Pk(G)=Pk(G-e)-Pk(Ge),由假设可令：Pk(G-e)=kn+a1kn-1+an-1kn-1,且a1=-m+1;Pk(Ge)=kn-1+b1kn-2+bn-2kn-2,且b1=-m+1,Pk(G)=kn+(a1+1)k

6、n-1+(a1+b1)kn-2+bn-2kn-2,Pk(G)中kn-1的系数a1+1=-m；Pk(G)中具有非零系数的k的最小次数为n-2即为G的分支数。(2)一个多项式，若是某个图的色多项式，那么也是该图对应的底图的色多项式。故我们仅需对单图来证明。若Pk(G)=k4-3k3+3k2是某个单图G的色多项式，则由(1)可知，m(G)=3，从而(G)2,另一方面，P1=1，这说明(G)1,与上面结论相矛盾，故Pk不可能是任何单图的色多项式。32.证明：因为G1和G2中分别有一个唯一的4度顶点：u1与v1.但是它们邻点状况不相同：u1有4个2度邻点，而v1只有两个2度顶点，所以G1与G2不同构。利

7、用直接计算方法可得：Pk(G1)=Pk(G2)=10k3+5k4+k5.33.证明：(1)当n=1时，Pk(K1)=k,命题成立。若nm时，命题均成立。设G是树，且n(G)=m.可知，存在悬挂边eE(G),于是G-e是孤立点加上顶点数为m-1的树，Ge是v(Ge)=m-1的树。由归纳法可知，Pk(G)=Pk(G-e)-Pk(Ge)=k2(k-1)m-2-k(k-1)m-2=k(k-1)m-1,故命题成立。(2)Pk(G-e)=Pk(G)+Pk(Ge),Pk(Ge)0,所以Pk(G-e)Pk(G),另一方面由于G连通，设T是G的生成树，逐次用上述导出的公式将余数T的边从G中除去，于是最后有Pk(

8、G)Pk(T),由(a)，Pk(T)=k(k-1)m-1,所以，Pk(G)k(k-1)m-1.若连通图G的Pk(G)=k(k-1)m-1时，则n=m-1,所以G是一棵树。即当且仅当G是树时等号才成立。第九章习题1. 解：每条边有2种定向方式，所以一个简单图共有2m(G)种定向。2.证明：不失一般性，设G是连通图。G中奇度顶点个数必然为偶数个，将偶数个奇度顶点配对，然后在每一对配对顶点间连一条边得到欧拉图G1，在G1中用Fluery算法求出G的一欧拉环游C，然后顺次在C上标上方向，由此得到C的定向图C1.在C1中，去掉添加的边后，得到G的定向图D，显然：对vV(D),有|d+(v)-d-(v)|1.7.解：强连通分支：1、2,3,5,6,7、4、9、8；单向连通分支：1,2,3,4,5,6,7、8,9；弱连通分支：1,2,3,4,5,6,7,8,9。11.证明：设该