图论 习题解答

图论第三次作业

2.证明：

根据欧拉公式的推论，有m≦l*(n-2)/(l-2), (1)若deg(f)≧4,则m≦4*(n-2)/2=2n-4;

(2)若deg(f)≧5,则m≦5*(n-2)/3,即：3m≦5n-10; (3)若deg(f)≧6,则m≦6*(n-2)/4,即：2m≦3n-6. 3.证明：

∵G是简单连通图，∴根据欧拉公式推论，m≦3n-6; 又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m≦2-n+3n-6=2n-4. 4.证明：

(1)∵G是极大平面图，∴每个面的次数为3， 由次数公式：2m==3φ, 由欧拉公式：φ=2-n+m, ∴m=2-n+m,即：m=3n-6. (2)又∵m=n+φ-2,∴φ=2n-4.

(3)对于n?3的极大可平面图的的每个顶点v，有d(v)?3，即对任一一点或者

子图，至少有三个邻点与之相连，要使这个点或子图与图G不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使w(G)?w(G?H)，由点连通度的定义知?(G)?3。

5.证明：

假设图G不是极大可平面图，那么G不然至少还有两点之间可以添加一条边e，

使G+e仍为可平面图，由于图G满足m?3n?6，那么对图G+e有m??3n?6，而平面图的必要条件为m??3n?6，两者矛盾，所以图G是极大可平面图。

6.证明：

(1)由?(G)?4知n?5当n=5时，图G为K5，而K5为不可平面图，所以n?6，

（由?(G)?4和握手定理有2m?4n，再由极大可平面图的性质m?3n?6，即可得n?6）对于可平面图有?(G)?5，而n?6，所以至少有6个点的度数不超过5.

(2)由?(G)?5和握手定理有

2m?5n，再由极大可平面图的性质

m?3n?6，即可得n?12，对于可平面图有?(G)?5，而n?12，所以至

少有12个点的度数不超过5.

8.证明：

(1)由握手定理?d(vi)?2m?n?(G)和极大可平面图的性质m?3n?6，可得

[6??(G)]n?12对n?4恒成立，又，所以6??(G)?3，即?(G)?3。

(2)由定理5，对简单可平面图都有?(G)?5，又图G是n?3的简单连通平面图，

所以G中至少有3个点的度数小于等于5.

(3)由定理5，对简单可平面图都有?(G)?5，又图G是n?4的简单连通平面图，

所以G中至少有4个点的度数小于等于5.

17.证明：

利用反证法，假设存在6连通可平面图， 设G是6连通图，则：k(G)≧6 由惠特尼定理可得：δ(G)≧k(G)≧6, ∴m>3n-6,这与G是简单平面图相矛盾， 因此假设不成立，不存在6连通可平面图 19.证明：

假设不存在面f,使得deg(f)≦5,则：2m=≧6φ, 由欧拉公式得：φ=2-n+m≦,于是得：2m≦3n-6,

另一方面，由δ(G)≧3得：2m≧3n>3n-6与上面得到结果相矛盾， 所以假设不成立，G至少存在一个面f,使得：deg(f)≦5.

第七章作业

2.证明：

设n=2k+1,∵G是Δ正则单图，且Δ>0, ∴m(G)==>kΔ,由定理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)∵

原图与该图同构，又，同构的图具有相同的色多项式， 所以原图色多项式为：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(G·e),

由假设可令：Pk(G-e)=kn+a1kn-1+…+an-1kn-1,且a1=-m+1; Pk(G·e)=kn-1+b1kn-2+…+bn-2kn-2,且b1=-m+1, ∴Pk(G)=kn+(a1+1)kn-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,另一方面，

本文来源：https://www.bwwdw.com/article/tggd.html