证明：非平凡树的最长轨道的起点和终点都是树叶
谁能证明？ 题证明：非平凡树的最长轨道的起点和终点都是树叶。
证用反证法。
假设最长轨道的起点和终点中，至少有一个不是树叶。这个不是树叶的点，
度数至少是 2 ，也就是说，至少会从这点伸出两条边。其中只可能有一条边，
连接到最长轨道，而伸出的另一条边，必定会连接到最长轨道以外的一个点
（假如连接的不是轨道外的点，而是轨道上的点，就会产生一个圈，不符合
已知这是一棵树的条件）。由于从端点伸出的一条边，连接到轨道外的一点，
所以，把这条伸出的边，以及连接到的轨道外的点，都加入到最长轨道中，
轨道的长度就会增加 1 ，于是，最长轨道可以变得更长，这就发生了矛盾。
因此，假设不成立，非平凡树的最长轨道的起点和终点必定都是树叶。 树叶=1
树=1
非平凡树的最长轨道起点终点都是树叶 谢谢陆老师！
页:
[1]