一个树,结点的度最多为k(k>=2),试证至少有k个树叶
问题描述：
一个树,结点的度最多为k(k>=2),试证至少有k个树叶
答
反证法.假设至多有s片树叶,s＜k.则这棵树有s个1度节点,1个k度节点,剩下的节点的度数都至少是2.
设结点个数是n,则边数m=n-1,由握手定理,2m=2n-2=∑d(Vi)≥s×1＋k×1+2(n-s-1),由此得s≥k.矛盾.
所以至少有k片树叶.