6．在一个有n个人的宴会上，每个人至少有m个朋友(2≤m≤n)。试证：有不少于m+1个人，使得他们按某种方法坐在一张圆桌旁，每人的左、右均是他的朋友。

8．设G是图。证明：若δ(G)≥2，则G包含长至少是δ(G)+1的圈。

P216习题

1．证明：若图G不是连通图，则Gc 是连通图。

2．证明：每一个自补图有4n或4n+1个顶点。

P228习题

1.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有：degu+degv≥9。

2．试求Kp中不同的哈密顿圈的个数。

4．完全偶图Km，n为哈密顿图的充分必要条件是什么？

10．证明具有奇数顶点的偶图不是哈密顿图。

16

第七章 树和割集

P243习题

1．分别画出具有4、5、6个顶点的所有树(同构的只算一个)。

2．证明：每个非平凡树是偶图。

3．设G是一棵树且Δ(G)≥k，证明：G中至少有k个度为1的顶点。

4．令G是一个有p个顶点，k个支的森林，证明：G有p-k条边。 6．设树T中有2n个度为1的顶点，有3n个度为2的顶点，有n个度为3的顶点，则这棵树有多少个顶点和多少条边？

7一棵树T有n2个度为2的顶点，n3个度为3的顶点，?，nk个度为k的顶点，则T有多少个度为1的顶点？

P257习题

1. P个顶点的图中，最多有多少个割点？

3．证明：有一座桥的三次图中至少有10个顶点。

4.设v是图G的一个割点，证明v不是G的补图Gc的割点。

7.有割点的连通图是否一定不是欧拉图？是否一定不是哈密顿图？有桥的连通图是否一定不是欧拉图和哈密顿图。

17

第八章 连通度和匹配

P264习题

1. 设G是一个有p个顶点的图，?(G)?(p?k?1)/2p?2。试证：G是k?连通的，

其中k?p。

6. G是一个三次正则图，试证：k(G) = ?(G)。

r7. 设r?2, G是r-正则图且k(G)=1。试证：?(G)?[]。

2

第九章 平面图和图的着色

P281习题

1.设G?(p,q)是一个具有f个面，k个分支的平面图，则p?q?f?k?1。

18

2. 若G是顶点数p≥11的平面图，试证Gc不是平面图。

4．证明：不存在7条棱的凸多面体。

P294习题

1.设G是一个没有三角形的平面图。应用欧拉公式证明G中有一个顶点v，使得degv ≤3。

2.设G是一个没有三角形的平面图。应用数学归纳法证明G是4－可着色的。

第十章 有向图

P301习题

2.画出具有三个顶点的所有互不同构的有向图的图解。

19

3.具有p个顶点的完全有向图中有多少条弧？

P307习题

1.设D是一个有p个顶点q条弧的有向图。若D是连通的，证明：p-1≤q≤p(p-1)。

2.设D是一个有p个顶点q条弧的强连通的有向图，则q至少是多大？

P307习题

2.有向图D的图解如图10.4.3所示

(1)写出D的邻接矩阵及可达矩阵；(2)写出D关联矩阵。

3.设D为图10.4.4中的有向图，试求v2到其余每个顶点的长≤4的所有通道的条数。

P321习题

1.设T是一个正则m元有序树，它有n0个叶子，T有多有多少条弧？

20