设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是 。

设无向图G是由k(k≥2)棵树组成的森林，已知G中有n个结点、m条边．试证明：

  m=n-k．

设无向图G是由k(k≥2)棵树组成的森林，已知G中有n个结点，m条边．试证明．m=n-k．

设G是具有k个连通分支的平面图，若G有n个结点、m条边、r个面，则必有(  )．

  A．n-m+r=k  B．n-m+r=k-1

  C．n-m+r=k+1  D．n-m+r=2

设G是具有k个连通分支的平面图，若G有n个结点，m条边，r个区域，则必有(  )．

  A．n-m+r=k  B．n-m+r=k-1

  C．n-m+r=k+1 D．n-m+r=2

G为(n，m)图，其中有n_k个结点的次数为k，其余结点的次数均为k+1，试证明：n_k=(k+1)·n-2m(其中n为图G的结点数目，m为边数)．

已知一棵树边的集合为{＜I,M＞,＜I,N＞,＜E,I＞,＜B,E＞,＜B,D＞,＜A,B＞,＜G,J＞,＜G,K＞,＜C,G＞,＜C,F＞,＜H,L＞,＜C,H＞,＜A,C＞},问这棵树中结点G的双亲结点为()

A.A

B.C

C.I

D.B

已知一棵树边的集合为{＜i，m＞，＜i，n＞，＜e，i＞，＜b，e＞，＜b，d＞，＜a，b＞，＜g，j＞，＜g，k＞，＜c，g＞，＜c，f＞，＜h，l＞，＜c，h＞，＜a，c＞}。

  请画出这棵树，并回答下列问题：

（1）哪个是根结点？

（2）哪些是叶结点？

（3）哪个是g的双亲？

（4）哪些是g的祖先？

（5）哪些是g的孩子？

（6）哪些是e的子孙？

（7）哪些是e的兄弟？哪些是f的兄弟？

（8）结点b和n的层次各是多少？

（9）树的深度是多少？

（10）以结点c为根的子树的深度是多少？

（11）树的度数是多少？

A、n/2

B、n(n+1)

C、nk

D、n(k+1)-2m

证明定理17.18.

定理17.18:设G*是具有h(k≥2)个连通分支的平面图G的对偶图,n*m*,r*和n,m,r分别为G*和G的顶点数,边数,面数,则

(1)n*=r,(2)m*= m;(3)r*=n-k+1;

(4)设G*的顶点v_t*，位于G的面R_t中,则d_G*(v_t*)=dcg(R_t).