习题一 1. （题 14）：证明图 1-28 中的两图是同构的 图 1-28 证明 将图 1-28 的两图顶点标号为如下的(a)与(b)图 v1 u1 v2 v6 v7 v10 v5 v8 v9 v3 (a) v4 u6 u8 u5 u3 u2 u10 u7 u9 (b) u4 作映射 f : f(vi)ui 容易证明，对vivjE((a)),有 f(vivj)uiujE((b)) (1 i  10, 1j 10 ) (1 i  10) 由图的同构定义知，图 1-27 的两个图是同构的。 2. （题 6）设 G是具有 m条边的 n阶简单图。证明：m =    n 2    当且仅当 G是 完全图。 证明 必要性 若 G 为非完全图，则 vV(G),有 d(v) n-1   d(v)  n(n-1)  2mn(n-1)  m  n(n-1)/2=    n 2    , 与已知矛盾！ 充分性 若 G 为完全图，则 2m= d(v) =n(n-1)  m=    n 2    。 3. （题 9）证明：若 k正则偶图具有二分类 V= V1∪V2，则 | V1| = |V2|。 

证明 由于 G 为 k正则偶图，所以，k V1 4. （题 12）证明：若δ≥2，则 G包含圈。  =m = k V2   V1= V2 。 证明 只就连通图证明即可。设 V(G)=｛v1,v2,…,vn｝,对于 G 中的路 v1v2… vk,若 vk 与 v1 邻接，则构成一个圈。若 vi1vi2…vin 是一条路，由于 2，因此，对 vin，存在点 vik 与之邻接，则 vikvinvik 构成一个圈 。 5. （题 17）证明：若 G不连通，则G 连通。 证明 对 _ G 中 连通；若 u 与 v 属于 g 的同一连通分支，设 w 为 G 的另一个连通分支中的一个顶 ,若 u 与 v 属于 G 的不同连通分支，显然 u 与 v 在 _ , GVvu   ) ( 点，则 u 与 w，v 与 w 分别在 _ G 中连通，因此，u 与 v 在 _ G 中连通。 习题二 2、证明：每棵恰有两个 1 度顶点的树均是路。 证明：设树 T 为任意一个恰有两个 1 度顶点的树，则 T 是连通的，且无圈，令 V1 、V2 为度为 1 的顶点，由于其他的顶点度数均为 0 或者 2，且 T 中无圈，则从 V1 到 V2 有 且只有一条连通路。所以，每棵恰有两个 1 度顶点的树均是路。得证。 5、证明：正整数序列 ( , dd 1 2 ,..., nd ) 是一棵树的度序列当且仅当 n  d i i 1  (2 n  )1 。 证明：设正整数序列 ( , dd 1 2 ,..., nd ) 是一棵树 T 的度序列，则满足 的边数，又有边数和顶点的关系  En 1 ，所以 n   i 1  d i  (2 n  )1 n  d i i 1  2 E ，E 为 T 14、证明：若 e 是 nK 的边，则 ( K n  e )  ( n  )2 n n  3 。 若 e 为 Kn 的一条边，由 Kn 中的边的对称性以及每棵生成树的边数为 n-1，Kn 的所有 生 成 树 的 总 边 数 为 ： ( n  )1 nn  2 ， 所 以 ， 每 条 边 所 对 应 的 生 成 树 的 棵 数 为 ： n  )1  ( nn ( n 1 2 n  2 )1  2 n n  3 ，所以，K n - e 对应的生成树的棵数为： ( K n  e )  n n  2  2 n n  3  ( n  )2 n n  3 16、Kruskal 算法能否用来求： （1）赋权连通图中的最大权值的树？ （2）赋权图中的最小权的最大森林？如果可以，怎样实现？ 

解：（1）不能，Kruskal 算法得到的任何生成树一定是最小生成树。 （2）可以，步骤如下： 步骤一：选择边 e1，是的 ( 1e 尽可能小； ) 步骤二：若已选定边 , 2 ee 1 ,..., ie ，则从 ,{\ eeE 1 2 ,... ie } 选取 1ie ，使 a、 b、 , eeG 2 [{ 1 ,... ie 1 }] 为无圈图 1ie 是满足 a 的尽可能小的权； ) ( 步骤三：当步骤二不能继续执行时停止； 习题三 3.设 G 是阶大于 2 的连通图，证明下列命题等价： （1）G 是块 （2）G 无环且任意一个点和任意一条边都位于同一个圈上； （3）G 无环且任意三个不同点都位于同一条路上。 证明：（1）→（2）： G 是块，任取 G 的一点 u，一边 e，在 e 边插入一点 v，使得 e 成为两条边，由此得到 新图 1G ，显然 1G 的是阶数大于 3 的块，由定理，G 中的 u,v 位于同一个圈上，于是 1G 中 u 与边 e 都位于同一个圈上。 (2)→(3): 无环，且任意一点和任意一条边都位于同一个圈上，任取 的点 u，边 e，若 在 上， 则三个不同点位于同一个闭路，即位于同一条路，如 不在 上，由定理， 的两点在同一个 闭路上，在 边插入一个点 v，由此得到新图 ，显然 的是阶数大于 3 的块，则两条边的 三个不同点在同一条路上。 (3)→(1): 连通，若 不是块，则 中存在着割点 ，划分为不同的子集块 , , , 无环， x  , v y 1  ，点 在每一条 v 2 的路上，则与已知矛盾， 是块。 13、设 H 是连通图 G 的子图，举例说明：有可能 k(H)> k(G). 解：通常 . 

e H 整个图为 ，割点 左边的图 为 的的子图， ， 则 . 15、设 T 是简单连通图 G 的生成树， )(TEGT   称为 G 的余树，图 G 的极小边割是指其 任何真子集均不是边割的边割。证明： （1）T 不含 G 的极小边割。 （2） eT  包含 G 的唯一的极小边割，其中 e 为 G 的不在T 中的边。 证明：（1）设T 含有 G 的极小边割 S，则 T 中不含极小边割 S，由于 T 是简单连通图 G 的生 成树，则 T 中必然含有一组极小割边，这与 T 中不含极小割边相矛盾，则T 中不含 G 的极小 边割。 （2）假设 e 为T 中的一条边，根据（1）得T +e 中仍不含 G 的极小割边，这与 eT  包含 G 的唯一的极小边割相矛盾，则 e 为 G 的不在T 中的边，得证。