西安电子科技大学$6.7.1 无向树软件学院案定理！任一棵非平凡树中至少有两片树叶。证明：设非平凡树T=<V,E>，|V|=n，IEl=m。由于T是连通的，因此对任意VEV，deg(v)1，且有deg(v)=2m=2(n-1)=2n-2。2F(i）若T中没有树叶，则每个结点的度数均大于等于2。则有：Z deg(v) ≥2n-V这与Zdeg(v）=2n-2矛盾。-(ii）若T中仅有一片树叶，而其它结点的度数均大于等于2。则有： deg(v) ≥2 (m-1)+1=2n-1这与Zdeg(v）=2n-2也矛盾。西安电子科技大学 §6.7.1 无向树 软件学院