证明顶点数大于等于2的无向树,至少有两片树叶

Question

证明顶点数大于等于2的无向树,至少有两片树叶

Answer 1

证明：
1.首先证明该无向树有叶子,用反证法
假设树没有叶子（即每个节点的度数>=2),这棵树有N个节点,
我们可以构造一条路径,这条路径存在环,与树的定义矛盾.
构造方法如下：
任选图中一个节点X1和一条边P,这条边连接着X2,由于X2的度数>=2,选出一条不同的P的边,这条边连着X3,
以此下去,一共选出N+1个节点.X1-P1-X2-P2-X3-P3.Xn-Pn-Xn+1
由于树中仅N个节点,那么X1到Xn+1中一定有两个是相同的,也就是这条路径中存在环.
2.证明叶子数不能为1
思路与上面相同,假设叶子数目为1,我们选X1为树中的叶子节点(根据假设,如果仅X1为叶子,则其他所有节点的度数>=2).后面方法同上,可以证明如果仅一个叶子,必然存在环.
综合1,2,可以证明树中至少有两片叶子.