2．在图6.5.5所示的图中，找一条欧拉迹。
3．某展览馆共有36个展室，布置如图6.5.6所示。有阴影的展室陈列实物，没有阴影的展室陈列图片。邻室之间都有门可以通行。有人希望每个展室都参观一次且仅一次，请你替他设计一条参观路线。
P228习题
1.给出一个10个顶点的非哈密顿图的例子，使得每一对不邻接的顶点u和v，均有：degu+degv≥9。
2．试求Kp中不同的哈密顿圈的个数。
3．试证：图6.6.6中的图不是哈密顿图。
4．完全偶图Km，n为哈密顿图的充分必要条件是什么？
5．设G是一个p(p≥3)个顶点的图。u和v是G的两个不邻接的顶点，并且
degu+degv≥p
26
证明：G是哈密顿图当且仅当G+uv是哈密顿图。
10．证明具有奇数顶点的偶图不是哈密顿图。
第七章 树和割集
P243习题
1．分别画出具有4、5、6个顶点的所有树(同构的只算一个)。
2．证明：每个非平凡树是偶图。
3．设G是一棵树且Δ(G)≥k，证明：G中至少有k个度为1的顶点。
27
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的顶点？
P252习题
1．设G是一个连通图。试证：G的子图G1是G的某个生成树的子图，当且仅当G1没有圈。
2.证明：连通图的任一条边必是它的某个生成树的一条边。
28
P257习题
1.P个顶点的图中，最多有多少个割点？
2．证明：恰有两个顶点不是割点的连通图是一条路。
3．证明：有一座桥的三次图中至少有10个顶点。
4.设v是图G的一个割点，证明v不是G的补图Gc的割点。
7.有割点的连通图是否一定不是欧拉图？是否一定不是哈密顿图？有桥的连通图是否一定不是欧拉图和哈密顿图。
第八章 联通度和匹配
P264习题
1．设G是一个有p个顶点的图，δ(G)≥((p+k)-1)/2，试证：G是k-连通的。
29
2．若(p，q)图G是k-边连通的，试证：q≥kp/2。
7．设r≥2，G是r正则图且χ(G)=1。证明：λ(G)≥[r/2]。
8．构造一个图G，使得χ(G)=3，λ(G)=4，δ(G)=5。
第九章 平面图和图的着色
P281习题
1.设G?(p,q)是一个具有f个面，k个分支的平面图，则p?q?f?k?1。
30