图论第三次作业
一、第六章
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.
二、第七章 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)