定理:设T是m阶非平凡的无向树,则T中 至少有两片树叶。 证:因为T是非平凡树所以T中每个顶点的度 数都大于等于1,设T有k片树叶,则有(n-k) 个顶点度数大于等于2,由握手定理可知 2m∑d(v;)≥k+2(n-k) 由m=n-1,将此结果代入上式后解得k≥2定理： 设T是n阶非平凡的无向树，则T中 至少有两片树叶。 证 : 因为T是非平凡树,所以T中每个顶点的度 数都大于等于1, 设T有k片树叶, 则有(n-k) 个顶点度数大于等于2,由握手定理可知 2m=∑d(vi ) ≥ k+2(n-k) 由m=n-1,将此结果代入上式后解得 k ≥ 2