运筹学讲义 (对v作数归法)当v=1,2时,结论显然成立 设当v=k时结论成立,则当v=k+1时,令v(T)=k+1,则由Thl v知,T至少有两个悬挂点不妨取其一为v,则易见T-v仍是树,且 (7-v)=k 由归纳假设,有E(T-v)=(T-v)-1=k-1 于是,E(T)=E(T-)+1=k-1+1=k=v(T)-1.综上,E 仁设T无圈,且E=ν-1,则仅需证T连通.(反证法)假设T不连通,则o(T)≥2.不妨设T的 各连通分支为T1,T2,…,T。,则易见T是树,且由(1)→(2)知,E(T)=v(T)-1,=1,2,…,O c≥2 于是,6()=∑a(7)=∑[(T)-1=∑()-0=v()-0≤(7)-2,与E=v-1矛盾 (1)分(3):→设T是树,则T连通:再由(1)→(2)知,E=V-1 ←设T连通,且E=v-1,则仅需证T无圈 (对v作数归法)当v=1,2时,E=0,1,T显然无圈; 设当v=k时无圈性成立,则当v=k+1时,令v(T)=k+1 E(T)=E(T)-1=k,则由Lema2(2)知,T至少有一个悬挂点不 妨设它为v,则易见T-v仍连通,且v(T-v)=(T)-1=k, T-v)=E(T)-1=k-1=v(T-v)-1 由归纳假设知,T-ν无圈.显然,T亦无圈.综上,T无圈得证 (1)◇(4):→设T是树,则T连通,∴T的任两顶点之间必至少有一条路相连 下证唯一性(反证法)假设彐u,v∈V(T),a,v之间有两条不同的路P,Q相连,运 筹 学 讲 义 5 （对  作数归法）当  = 1,2 时，结论显然成立； 设当  = k 时结论成立，则当  = k +1 时，令  (T) = k +1 ，则由 Th1 知， T 至少有两个悬挂点.不妨取其一为 v ，则易见 T −v 仍是树，且  (T − v) = k . 由归纳假设，有  (T − v) = (T − v) −1 = k −1. 于是，  (T) =  (T − v) +1 = k −1+1 = k = (T) −1.综上，  = −1 成立.  设 T 无圈，且  = −1,则仅需证 T 连通.（反证法）假设 T 不连通，则 (T)  2 .不妨设 T 的 各连通分支为 T T T , , , 1 2  ，则易见 Ti 是树，且由（1）  （2）知，  (Ti ) = (Ti ) −1,i = 1,2,  , . 于是， ( ) ( ) [ ( ) 1] ( ) ( ) ( ) 2 2 1 1 1 = = − = − = −  −  = = = T  T  T  T T T i i i i i   i           ，与  = −1 矛盾. （1）  （3）：  设 T 是树，则 T 连通；再由（1）  （2）知，  = −1.  设 T 连通，且  = −1 ，则仅需证 T 无圈. （对  作数归法）当  = 1,2 时，  = 0,1，T 显然无圈； 设当  = k 时无圈 性成 立， 则当  = k +1 时， 令  (T) = k +1 ，  (T) =  (T) −1 = k ，则由 Lemma2（2）知， T 至少有一个悬挂点.不 妨设它为 v ，则易见 T −v 仍连通，且  (T − v) = (T) −1 = k ，  (T − v) =  (T) −1 = k −1 = (T − v) −1. 由归纳假设知， T −v 无圈.显然， T 亦无圈.综上， T 无圈得证. （1）  （4）：  设 T 是树，则 T 连通，  T 的任两顶点之间必至少有一条路相连. 下证唯一性.（反证法）假设 u,v V(T) ，u, v 之间有两条不同的路 P,Q 相连