T是G的子图,G有n个顶点.求证,当T有n个顶点和n-1条边的时候,T是一个生成树少了一个条件：T是G的连通子图

T是G的子图,G有n个顶点.求证,当T有n个顶点和n-1条边的时候,T是一个生成树少了一个条件：T是G的连通子图
T是G的子图,G有n个顶点.求证,当T有n个顶点和n-1条边的时候,T是一个生成树
少了一个条件：T是G的连通子图

T是G的子图,G有n个顶点.求证,当T有n个顶点和n-1条边的时候,T是一个生成树少了一个条件：T是G的连通子图
当n=1,2时,显然成立
归纳假设当n=k时,结论成立
当n=k+1时
T有k+1个顶点,k条边,且T连通.
若每个顶点的度数都大于等于2（即从这个顶点引出的边数）
则总度数大于等于2k+2,即边数>=k+1（因为每条边有两个顶点,即计算两次）这不可能
所以必有顶点的度数小于等于1
而T是连通图,即每个顶点的度数都大于等于1
即必有顶点A的度数是1,记这条边为AB
考虑去掉顶点A和边AB的图T‘,
记G'是去掉顶点A和与之相连的所有边后的图,则
T’是G'的连通子图,且T‘有k个顶点,k-1条边
由归纳假设知,T’是G'的生成树
故T是G的生成树,结论成立
从而对任意正整数n,结论成立