The number of leaves
Task number: 4215
Prove that if there is a vertex of degree \( k \) in a finite tree, then the tree has at least \( k \) leaves.
Solution
For \( k \le 1 \) the statement holds, so consider \( k \ge 2 \) and a vertex \( v \) of this degree.
Repeat \( k \) times the following operation. Removing an edge from \( v \) creates two components. One of these components does not contain \( v \). This component is a tree, so it is either a single vertex that was itself a leaf before the edge was removed, or this tree has some edges and in this case contains at least two leaves. At most one of these leaves could be a neighbor \( v \), the others were leaves even before the edge was removed.
We found at least one leaf behind each edge removed, so the tree must have at least \( k \) leaves.
