一个树,结点的度最多为k(k>=2),试证至少有k个树叶
人气：224 ℃ 时间：2019-10-17 06:11:57
解答
反证法.假设至多有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片树叶.
推荐
- * 确定方程x1+x2+x3=14的使得每个xi(i=1,2,3)都不超过8的非负整数解的个数
- 设A={1,2,3,4,5},A上的偏序关系.R={,,,,,}∨IA (1)作出偏序关系R的哈斯图 (2)令B={1,2,3,4,5}求B的最大最小元,极大极小远,上界,上确界,下界,下确界.
- 两道离散数学问题,求大神解答
- 设集合A={a,b,c,d,e,f,g},A的一个划分 ={{a,b},{c,d,e},{f,g}},则 所对应的等价关系有____个二元组.
- 二、在某班的班委选举中,已知阚志强、商利利、王红红三人是班委的候选人,选举时发现：
- 求函数y=｜3+2sin(∏/4-x/2)｜的单调增区间
- 这句话用英文怎么说合适啊?
- 读数和写数从什么位起
猜你喜欢
