(2)证明∑m只依赖于树T的顶点数。 48不含圈的图称为森林( forest),证明: (1)G是森林当且仅当E=v-w;(2)无孤立点的森林至少有2w个1度顶点。 这里w表示G的连通分支数,孤立点指零度顶点。 49证明:具有m条边的任意n顶点图至少有m-n+1个圈 50令T是一棵n顶点数,对于2≤i≤k的每个i值,树中有一个度为i的顶点;其余的n-k+1个 顶点都是叶子。确定n并表示成k的形式 51令T是一棵非平凡树,其中所有与叶子相邻的顶点的度至少为3,证明:T中某一对叶子有公共 的相邻顶点 52令G是一个连通的n顶点图,证明:G恰有一个圈当且仅当G恰有n条边 53令T是一棵树,证明:T的顶点全为奇度点当且仅当对ve∈E(T),T-e的两个连通分支都具 有奇数的阶 4令T是一棵阶为偶数的树,证明:T恰有一个生成子图使得其中每个顶点的度均为奇数。 55证明:若T是一个具有k条边的树,G是一个简单图且o(G)≥k,则G含有与T同构的子图。 56令G是一棵树,其中2k个顶点具有奇数度,证明:G可分解成k条路。 57对n≥4,令G是满足(G)≥2n-3的简单n点图,证明:G有两个等长的圈 58令u是连通图G的一个顶点,证明不可能选出从u到其他各顶点的最短路使得这些路的并是 棵树。 59令T、T是连通图G的两棵生成树,对于e∈E(T)-E(T"),证明存在一条边e’∈E(T)-E(T), 使得T+e-e和T-e+e’都是G的生成树。 60设G是一个加权的连通图并且其各边上的权值互不相同。不使用 Kruskal算法,证明:G只有 棵权值最小的生成树(提示:利用上题结论)。 61为n阶完全图Kn的所有边分配整数权值。假设一个圈的权值是该圈上所有边的权值之和。证明: 所有圈的权值均为偶数当且仅当具有奇数权值的那些边构成的子图是一个生成二部图。(提示 对于具有偶数权值的边构成的子图,其任意连通分量都是一个完全图)。 62求下图中从l到其余各点的最短路。 63修改 Kruskal算法用以（2）证明 1 i i in ∞ = ∑ 只依赖于树 T 的顶点数。 48 不含圈的图称为森林（forest），证明： （1）G 是森林当且仅当ε =ν − w ；（2）无孤立点的森林至少有 2w 个 1 度顶点。 这里 w 表示 G 的连通分支数，孤立点指零度顶点。 49 证明：具有 m 条边的任意 n 顶点图至少有 m n − +1个圈。 50 令 T 是一棵 n 顶点数，对于 2 ≤ ≤i k 的每个 i 值，树中有一个度为 i 的顶点；其余的 n k − +1个 顶点都是叶子。确定 n 并表示成 k 的形式。 51 令 T 是一棵非平凡树，其中所有与叶子相邻的顶点的度至少为 3，证明：T 中某一对叶子有公共 的相邻顶点。 52 令 G 是一个连通的 n 顶点图，证明：G 恰有一个圈当且仅当 G 恰有 n 条边。 53 令 T 是一棵树，证明：T 的顶点全为奇度点当且仅当对∀e ET ∈ ( ) ，T e − 的两个连通分支都具 有奇数的阶。 54 令 T 是一棵阶为偶数的树，证明：T 恰有一个生成子图使得其中每个顶点的度均为奇数。 55 证明：若 T 是一个具有 k 条边的树，G 是一个简单图且δ ( ) G k ≥ ，则 G 含有与 T 同构的子图。 56 令 G 是一棵树，其中 2k 个顶点具有奇数度，证明：G 可分解成 k 条路。 57 对 n ≥ 4 ，令 G 是满足ε () 2 3 G n ≥ − 的简单 n 点图，证明：G 有两个等长的圈。 58 令 u 是连通图 G 的一个顶点，证明不可能选出从 u 到其他各顶点的最短路使得这些路的并是一 棵树。 59 令 T、T′ 是连通图 G 的两棵生成树，对于e ET ET ∈ () ( ) − ′ ，证明存在一条边e ET ET ′ ′ ∈ − ( ) () ， 使得T ee ′ ′ + − 和Tee − + ′ 都是 G 的生成树。 60 设 G 是一个加权的连通图并且其各边上的权值互不相同。不使用 Kruskal 算法，证明：G 只有一 棵权值最小的生成树（提示：利用上题结论）。 61 为 n 阶完全图 Kn 的所有边分配整数权值。假设一个圈的权值是该圈上所有边的权值之和。证明： 所有圈的权值均为偶数当且仅当具有奇数权值的那些边构成的子图是一个生成二部图。（提示： 对于具有偶数权值的边构成的子图，其任意连通分量都是一个完全图）。 62 求下图中从 u0 到其余各点的最短路。 63 修改 Kruskal 算法用以： u0 u1 u2 u3 u4 u5 u6 u7 1 2 2 2 3 3 1 3 4 4 4 5 6 6 7 7 8