证明：非平凡树的最长轨道的起点和终点都是树叶

wilsony

谁能证明？

luyuanhong

题  证明：非平凡树的最长轨道的起点和终点都是树叶。

证  用反证法。

    假设最长轨道的起点和终点中，至少有一个不是树叶。这个不是树叶的点，

度数至少是 2 ，也就是说，至少会从这点伸出两条边。其中只可能有一条边，

连接到最长轨道，而伸出的另一条边，必定会连接到最长轨道以外的一个点

（假如连接的不是轨道外的点，而是轨道上的点，就会产生一个圈，不符合

已知这是一棵树的条件）。由于从端点伸出的一条边，连接到轨道外的一点，

所以，把这条伸出的边，以及连接到的轨道外的点，都加入到最长轨道中，

轨道的长度就会增加 1 ，于是，最长轨道可以变得更长，这就发生了矛盾。

    因此，假设不成立，非平凡树的最长轨道的起点和终点必定都是树叶。

数学大神爱解题

树叶=1
树=1
非平凡树的最长轨道起点终点都是树叶

wilsony

谢谢陆老师！