A tree has at least as many leaves as its maximum degree
Statement
A tree is a connected graph without cycles. A leaf is a vertex of degree .
- Prove that a tree with vertices has exactly edges.
- Prove that if a tree has a vertex of degree , then it has at least leaves.
Hint
For part 1, remove a leaf. For part 2, use the handshake lemma .
Show solutionHide solution
Solution
1. First, a tree with vertices has a leaf: take a longest path in the tree. The vertex has no neighbour outside the path and no neighbour with (that would create a cycle), so its only neighbour is .
Now induct on . For the tree is one edge. For , remove a leaf and its edge: the remaining graph is still connected and acyclic, with vertices and, by induction, edges. So the original tree has edges.
2. Let be a vertex of degree . If , then the tree has at least one leaf (indeed at least when ), so the claim holds trivially. Assume . Let be the number of leaves. Each leaf has degree ; has degree ; all other vertices are not leaves and have degree at least . By the handshake lemma and part 1,
Simplifying the right side: . Therefore , i.e. .
Equality. It holds when all vertices other than and the leaves have degree exactly , that is when the tree is a "spider": paths glued at .
Lesson. Handshake lemma: relate the degrees to the number of edges.