第三章
1.证明： 必要性：
v 是连通图G 的割边， 则
， 至少有两个连通
分支。

设其中一个连通分支顶点集合为V1,另外连通分支顶点集合为V2,即V1与V2构成V 的划分。

对于任意的u ∈V1, v ∈V2，如果割边e 不在某一条（u ，v ）路上，那么，该路也是连接G-e 中的u 与v 的路，这与u,v 处于G-v 的不同分支矛盾。

“充分性”
若e 不是图G 的割边，那么G-v 连通，因此在G-v 中存在u,v 路，当然也是G 中一条没有经过边e 的u,v 路。

矛盾。

7.证明： v 是单图G 的割点，则G-v 至少两个连通分支。

现任取 , 如果x,y 在G-v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，通过u ，可说明，x 与y 在G-v 的补图中连通。

若x,y 在G-v 的不同分支中，则它们在G-v 的补图中邻接。

所以，若v 是G 的割点，则v 不是其补图的割点。

9.连通图G 的一个子图B 称为是G 的一个块，如果(1), 它本身是块；(2), 若没有真包含B 的G 的块存在。

又由于对于阶数至少是3的
()()G e G ωω->
图G是块当且仅当G无环并且任意两点都位于同一圈上。

根据题意，对于阶数至少是3的图G，由于G没有偶圈，所以G的每个块的点可以在奇圈上，如果不在奇圈上，则块只能是K2，否则如果不是K2的话，该子图将存在割点，该子图就不是块。

得证。

16.（1）
（2）
（3）
第四章3. （1）既是欧拉闭迹又是哈密尔顿圈
（2）
（3）
（4）
7.由于图没有奇度顶点，所以是欧拉图，又定理1可得，图G的边集可以划分为圈C1，C2，。

Cm，所以E（G）可以表示成C1，C2.。

Cm的并。

10.若图不是二连通，则存在割点，由于哈密尔顿图不存在割点，因而G是非哈密尔顿图。

若G是具有二分类（X,Y）的偶图，且|X|不等于|Y|，设X中所有点为x1，x2.。

xm，Y中的所有点为y1，y2.。

yn，若存在哈密尔顿图，则在哈密尔顿圈中必然存在X中的点与Y中的点相互交替出现，但是|X|不等于|Y|，则必然出现某两个点同属于|X|或者|Y|，但是G是偶图，属于同一集合的这样的两个点不可以相连，所以存在哈密尔顿圈矛盾，因而不存在哈密尔顿圈。

12. 证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1
G1的度序列为：(d1+1,d2+1,…,dn+1, n)
由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且dn-m+1+1<n-m+1=(n+1)-m。

于是由度序列判定定理知：G1是H图，得G有H路。

第五章
1.（1）证明一：
证明每个k方体都是k正则偶图。

事实上，由k方体的构造：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。

如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。

显然，X中顶点互不邻接，Y中顶点也如此。

所以k方体是偶图。

又不难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。

由推论：k方体存在完美匹配。

（2）我们用归纳法求K2n和Kn,n中不同的完美匹配的个数。

K2n的任意一个顶点有2n-1种不同的方法被匹配。

所以K2n的不同
完美匹配个数等于(2n-1)K2n-2,如此推下去，可以归纳出K2n的不同完美匹配个数为：(2n-1)!!
同样的推导方法可归纳出K n, n的不同完美匹配个数为：n!
2. 证明：若不然，设M1与M2是树T的两个不同的完美匹配，那么M1ΔM2≠Φ,且T[M1ΔM2]每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。

6.证明：由习题5第一题知：K2n的不同完美匹配的个数为(2n-1)!!。

所以，K2n的一因子分解数目为(2n-1)!!
7.将K9进行2因子分解，四个圈为
C1=p9 p1 p8 p2 p7 p3 p6 p4 p5 p9
C2=p9 p2 p1 p3 p8 p4 p7 p5 p6 p9
C3=p9 p3 p2 p4 p1 p5 p8 p6 p7 p9
C4=p9 p4 p3 p5 p2 p6 p1 p7 p8 p9
13. 最小权值和是30
19. 证明：K4n+1= K 2(2n)+1 , 所以，可以分解为2n个边不重的2
因子之和。

而任意2个2因子可以并成一个4因子。

所以，共可以并成n个4因子。

即K4n+1可以分解为n个4因子的和。