用△记G中顶点的最大度.证明:若G是△≥k的树,则G中至少有k个顶点的度为1.

Question

用△记G中顶点的最大度.证明:若G是△≥k的树,则G中至少有k个顶点的度为1.

Answer 1

考虑具有最大度数的顶点所在的连通子树,设其有n个顶点,可知其有n-1条边,顶点度数和2(n-1).
因其连通,每个顶点的度数≥1.设有m个顶点度数为1,则其余顶点度数≥2,且有一个度数≥k.
总度数2(n-1)≥m+2(n-m-1)+k,即有m≥k.