(1)→(2) 如果G是树,则G中任意两个顶点之间存在唯一的路径。 存在性。 由G的连通性及定理145的推论(在n阶图G中,若从顶点v到 (v;ν)存在通路,则v到v一定存在长度小于等于n1的初 级通路(路径)可知, u,v∈V,u与ν之间存在路径。 唯一性(反证法)。 若路径不是唯一的,设厂1与/2都是n到v的路径, 易知必存在由厂和2上的边构成的回路, 这与G中无回路矛盾
(1)(2) 如果G是树，则G中任意两个顶点之间存在唯一的路径。 存在性。 由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到 vj(vi vj)存在通路，则vi到vj 一定存在长度小于等于n-1的初 级通路(路径)）可知， u,v∈V，u与v之间存在路径。 唯一性（反证法）。 若路径不是唯一的，设Г1与Г2都是u到v的路径， 易知必存在由Г1和Г2上的边构成的回路， 这与G中无回路矛盾
(2)→(3) 如果G中任意两个顶点之间存在唯一的路径, 则G中无回路且m=n-1。 首先证明G中无回路。 若G中存在关联某顶点v的环, 则吨到w存在长为0和1的两条路经 注意初级回路是路径的特殊情况), 这与已知矛盾。 若G中存在长度大于或等于2的圈, 则圈上任何两个顶点之间都存在两条不同的路径, 这也与已知矛盾
(2)(3) 如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 首先证明 G中无回路。 若G中存在关联某顶点v的环， 则v到v存在长为0和1的两条路经 (注意初级回路是路径的特殊情况)， 这与已知矛盾。 若G中存在长度大于或等于2的圈， 则圈上任何两个顶点之间都存在两条不同的路径， 这也与已知矛盾
(2)→(3) 如果G中任意两个顶点之间存在唯一的路径, 则G中无回路且m=n-1。 其次证明m=m-1。(归纳法) n=1时,G为平凡图,结论显然成立。 设n≤k(k≥1)时结论成立, 当n=k+1时,设e=(u,吵为G中的一条边, 由于G中无回路,所以Ge为两个连通分支G、G20 设n、m分别为G中的顶点数和边数,则n≤k,i=1,2, 由归纳假设可知m=n-1,于是 m=m+m2+1=m1-1+n2-1+1=n1+n2-1=n-1
(2)(3) 如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 其次证明 m＝n-1。（归纳法） n＝1时，G为平凡图，结论显然成立。 设n≤k(k≥1)时结论成立， 当n=k+1时，设e＝(u,v)为G中的一条边， 由于G中无回路，所以G-e为两个连通分支G1、G2。 设ni、mi分别为Gi中的顶点数和边数，则ni≤k ，i＝1,2， 由归纳假设可知mi＝ni-1，于是 m＝m1+m2 +1＝n1 -1+n2 -1+1＝n1 +n2 -1＝n-1
(3)→(4) 如果G中无回路且m=m-1,则G是连通的且m=n-1。 只需证明G是连通的。(采用反证法) 假设G是不连通的,由s(s≥2)个连通分支GG2灬G组成,并 且G中均无回路,因而G全为树。 由(1)→(2)→(3)可知,m,=n;-1。于是, m=∑m=∑(m-1)=∑n-S=n-s 由于s≥2,与m=n-1矛盾
只需证明G是连通的。（采用反证法） 假设G是不连通的，由s(s≥2)个连通分支G1 ,G2 ,…,Gs组成，并 且Gi中均无回路，因而Gi全为树。 由(1)(2)(3)可知，mi ＝ni -1。于是， 由于s≥2，与m＝n-1矛盾。 1 1 1 ( 1) s s s i i i i i i m m n n s n s = = = = = − = − = − (3)(4) 如果G中无回路且m＝n-1，则G是连通的且m＝n -1
(4)→(5) 如果G是连通的且m=n1,则G是连通的且G中任何边均为桥 只需证明G中每条边均为桥。 Ve∈E,均有|E(G-e)|=m1-1=m2, 由习题十四题49(若G是n阶m条边的无向连通图,则mn1)可 知,Ge已不是连通图, 所以,e为桥
如果G是连通的且m＝n−1，则G是连通的且G中任何边均为桥。 只需证明G中每条边均为桥。 e∈E，均有|E(G-e)|＝n-1-1＝n-2， 由习题十四题49（若G是n阶m条边的无向连通图，则m≥n-1）可 知，G-e已不是连通图， 所以，e为桥。 (4)(5)