一个树,结点的度最多为k(k>=2),试证至少有k个树叶

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 12:38:24
一个树,结点的度最多为k(k>=2),试证至少有k个树叶一个树,结点的度最多为k(k>=2),试证至少有k个树叶一个树,结点的度最多为k(k>=2),试证至少有k个树叶反证法.假设至多有s片树叶,s<

一个树,结点的度最多为k(k>=2),试证至少有k个树叶
一个树,结点的度最多为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片树叶.