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的子图