图论及应用第一章完整作业(共7页).docx

习 题 11. 证明在n阶连通图中（1） 至少有n-1条边。（2） 如果边数大于n-1，则至少有一条闭通道。（3） 如恰有n-1条边，则至少有一个奇度点。证明 (1) 若对vV(G),有d(v)2,则：2m=d(v)2n mnn-1,矛盾！ 若G中有1度顶点，对顶点数n作数学归纳。 当n=2时，G显然至少有一条边，结论成立。 设当n=k时，结论成立， 当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。(2) 考虑v1v2vn的途径，若该途径是一条路，则长为n-1,但图G的边数大于n-1,因此存在vi,vj,使得viadgvj,这样，vivi+1vj并上vivj构成一条闭通道；若该途径是一条非路，易知，图G有闭通道。(3) 若不然，对vV(G),有d(v)2,则：2m=d(v)2n mnn-1,与已知矛盾！2. 设G是n阶完全图，试问（1） 有多少条闭通道？（2） 包