证明：如果 T 是树，且所有顶点度数的最大值 Δ(T)≥n ，则 T 至少有 n 片树叶

wilsony

谁能证明？

wilsony

陆老师愿意做下这道题吗？

luyuanhong

wilsony 发表于 2025-8-26 19:12
陆老师愿意做下这道题吗？

我不知道 Δ(T) 是什么意思。

wilsony

陆老师，

luyuanhong

题  证明：如果 T 是树，且所有顶点度数的最大值 Δ(T)≥n ，则 T 至少有 n 片树叶。

证  因为 T 中所有顶点度数的最大值 Δ(T)≥n ，所以在 T 中至少有一个顶点，它的

度数大于等于 n 。设想从这个顶点出发，每次添加一条边，逐步构成整棵树。

    因为这个顶点的度数大于等于 n ，所以从这个顶点至少会伸出 n 条边。这 n 条边

的另一个端点不会与已有的顶点重合，可见这 n 条边的另一个端点度数都是 1 ，也就是

说，这 n 个端点都是树叶，这时 T 至少有 n 片树叶。

    然后，在已有的点上逐步添加边。

    如果是在度数为 1 的点上添加一条边，原来度数为 1 的顶点变成度数为 2 ，少了一片

树叶，但是添加的一条边的另一个端点度数为 1 ，所以 T 上仍然至少有 n 片树叶。

    如果是在度数大于 1 的点上添加一条边，不会影响原来度数为 1 的顶点，原来的树叶不

会减少，而添加的一条边的另一个端点度数为 1 ，所以这时 T 上又增加了一片树叶。

    总之，每次添加一条边，树叶数都不会减少，所以，T 上始终可以保持至少有 n 片树叶。

wilsony

多谢陆老师！