Theorem 4.3 Every nontrivial tree has at least two end-vertices. Proof.Let T be a nontrivial tree and among all paths in T, let P be a path of greatest length. 口 Suppose that P is a u-v path,say P=(u=uo,u,...uk=v), where k=1.We show that u and v are end-vertices of G. Necessarily,neither u nor v is adjacent to any vertex not on P,for otherwise,a path of greater length would be produced.Certainly,u is adjacent to u on P and v is adjacent to uk-1 on P. Moreover,since T contains no cycles,neither u nor v is adjacent to any other vertices in P.Therefore,deg u=deg v=1
Theorem 4.3 Every nontrivial tree has at least two end-vertices. ◼ Proof. Let T be a nontrivial tree and among all paths in T, let P be a path of greatest length. ❑ Suppose that P is a u − v path, say P = (u = u0 , u1 , …, uk = v), where k ≥ 1. We show that u and v are end-vertices of G. ❑ Necessarily, neither u nor v is adjacent to any vertex not on P, for otherwise, a path of greater length would be produced. Certainly, u is adjacent to u1 on P and v is adjacent to uk −1 on P. ❑ Moreover, since T contains no cycles, neither u nor v is adjacent to any other vertices in P. Therefore, deg u = deg v = 1
Theorem 4.4 Every tree of order n bas size n-1. Proof.We proceed by induction on n. There is only one tree of order 1,namely K1,which has size 0.Thus the result is true for n=1. Assume for a positive integer k that the size of every tree of order k is k-1. Let Tbe a tree of order k+1.By Theorem 4.3,T contains at least two end-vertices.Let v be one of them.Then T=T-v is a tree of order k.By the induction hypothesis,the size of T'is m =k-1. Since Thas exactly one more edge than T,the size of Tis m+1 (k-1)+1=(k+1)-1,as desired
Theorem 4.4 Every tree of order n has size n − 1. ◼ Proof. We proceed by induction on n. ❑ There is only one tree of order 1, namely K1 , which has size 0. Thus the result is true for n = 1. ❑ Assume for a positive integer k that the size of every tree of order k is k − 1. ❑ Let T be a tree of order k + 1. By Theorem 4.3, T contains at least two end-vertices. Let v be one of them. Then T′ = T − v is a tree of order k. By the induction hypothesis, the size of T′ is m = k − 1. Since T has exactly one more edge than T′, the size of T is m + 1 = (k − 1) + 1 = (k + 1) − 1, as desired
关于树的另外一个性质 Theorem 4.9 Let T be a tree of order k.If G is a graph withδ（可≥k-1,then T is isomorphic to some subgraph of G
关于树的另外一个性质 Theorem 4.9 Let T be a tree of order k. If G is a graph with δ(G) ≥ k − 1, then T is isomorphic to some subgraph of G
Theorem 4.9 Let T be a tree of order k.If G is a graph with Image(G)=k-1,then T is isomorphic to some subgraph of G ■对k进行数学归纳法证明 ■奠基：K=1,2时显然成立：孤立点、一条边 ■假设：T有k-1点，H的最小度大于等于k-2,结论成立 ■归纳：T有k点，G的最小度大于等于k-1 口令V是T中端点，u是v的相邻点； 口从T中删除V,命名新树为T,T'同构与G的某个子图F。令u是F中u的同构点 DegG(u)>=k-1,而F只有k-1个点，u一定有一个 不属于V(F)的相邻点w,那么F基础上加上点W 以及uw边，构成一棵树F G 口T和F同构，F'是G的子图
Theorem 4.9 Let T be a tree of order k. If G is a graph with Image(G) ≥ k − 1, then T is isomorphic to some subgraph of G. ◼ 对k进行数学归纳法证明 ◼ 奠基：K=1,2时显然成立：孤立点、一条边 ◼ 假设：T’有k-1点，H的最小度大于等于k-2，结论成立 ◼ 归纳：T有k点，G的最小度大于等于k-1 ❑ 令v是T中端点，u是v的相邻点； ❑ 从T中删除v，命名新树为T’, T’同构与G的某个子图F。令u’是F中u的同构点 ❑ DegG(u’)>=k-1，而F只有k-1个点，u’一定有一个 不属于V(F)的相邻点w，那么F基础上加上点w 以及u’w边，构成一棵树F’ ❑ T和F’同构，F’是G的子图
树的性质的“极限性” a)Every edge of a tree is a cut-edge. b)Adding one edge to a tree forms exactly one cycle. c)Every connected graph contains a spanning tree. 间题4： 什么样的图生成树是唯一的，为什么？
树的性质的“极限性