Final answer:
To prove that a tree T with minimum degree δ(T)=k must contain at least k leaves, we examine the structure of a tree and the sum of degrees of its vertices, demonstrating the necessity for vertices with degrees less than k, which are typically leaves, to satisfy the degree sum formula for trees.
Step-by-step explanation:
The question is asking us to prove that a tree T with minimum degree δ(T)=k contains at least k leaves. A leaf is a vertex with degree 1. We can prove this statement using the concept of tree structure and degrees of vertices.
Consider a tree T with n vertices. Since T is a tree, it has exactly n-1 edges, as the number of edges in a tree is always one less than the number of vertices. Now, let's look at the sum of the degrees of all vertices, which is twice the number of edges due to each edge contributing to the degrees of two vertices. This sum is 2(n-1).
If k is the minimum degree, then there must be at least one vertex of degree k. Now, for the remaining n-1 vertices, if none was a leaf, it means they would all have a degree of at least k. This would result in the sum of degrees being at least kn, but we know the sum must be 2(n-1).
Therefore, there must be vertices with degrees less than k to balance out the vertex or vertices with degree k. The only vertices with degrees less than k in a tree are leaves (degree 1). As we have shown that the sum of degrees can only reach 2(n-1) when these lower-degree vertices are present, T must have at least k leaves to ensure the minimum degree of the tree remains k.