Question

一道离散数学证明题

设T为平凡无向树，T中度数最大的节点有两个，且度数K>=2，求证T叶子节点的数量>=2K-2。谢谢！
抱歉抱歉，原题打错了，是非平凡无向树，

Answer 1

1.因为每一个非根节点，要么有两个叶子，要么有一个叶子，最少的情况就是，只有一个叶子，且叶子也至多有一个子叶子。度数=n的节点，对应的最终叶子的数量>=n

2. 度数最大的节点必然是根节点的直接后继，否则必然导致矛盾。因为如果不是直接后继的话，那么它的父节点的叶子个数就比它大至少1了。
所以这两个度数"最大"的节点的度数=K-1，所以这两棵树的叶子的数量>2*(K-1)=2K-2

3.当然根节点还可以有其他的子数或者叶子，所以
T总叶子节点的数量>=2K-2

得证

Answer 2

设叶子节点的数量为X个，非叶子非度数最大的节点个数为Y个,最大的节点有两个，故全部节点为X+Y+2，由树的边数是节点数减1，故边数为X+Y+2-1=X+Y+1，所有节点的度数之和为边数的两倍，故所有节点的度数之和为2（X+Y+1），
非叶子非度数最大的节点度数至少为2度，故非叶子非度数最大的节点度数之和>=2Y，故
所有节点的度数之和=叶子节点度数之和+非叶子非度数最大的节点度数之和+度数最大的两个节点度数之和>=X+2Y+2K,
即2（X+Y+1）>=X+2Y+2K，由此得X>=2K-2。

Answer 3

确实