Maths WorkshopMaths problems with full solutions
Exercise 1239Combinatorics › Graph theoryOlympiadAdded 4 Nov 2026

A tree has at least as many leaves as its maximum degree

#trees#graphs#handshake lemma#degrees

Statement

A tree is a connected graph without cycles. A leaf is a vertex of degree 11.

  1. Prove that a tree with n≥2n\ge2 vertices has exactly n−1n-1 edges.
  2. Prove that if a tree has a vertex of degree kk, then it has at least kk leaves.
Hint

For part 1, remove a leaf. For part 2, use the handshake lemma ∑vdeg⁡v=2×#edges\sum_v\deg v=2\times\#\text{edges}.

Show solutionHide solution

Solution

1. First, a tree with n≥2n\ge2 vertices has a leaf: take a longest path v0v1…vmv_0v_1\dots v_m in the tree. The vertex v0v_0 has no neighbour outside the path and no neighbour viv_i with i≥2i\ge2 (that would create a cycle), so its only neighbour is v1v_1.

Now induct on nn. For n=2n=2 the tree is one edge. For n>2n>2, remove a leaf and its edge: the remaining graph is still connected and acyclic, with n−1n-1 vertices and, by induction, n−2n-2 edges. So the original tree has n−1n-1 edges.

2. Let vv be a vertex of degree k≥1k\ge1. If k=1k=1, then the tree has at least one leaf (indeed at least 22 when n≥2n\ge2), so the claim L≥kL\ge k holds trivially. Assume k≥2k\ge2. Let LL be the number of leaves. Each leaf has degree 11; vv has degree kk; all other n−L−1n-L-1 vertices are not leaves and have degree at least 22. By the handshake lemma and part 1,
2(n−1)=∑udeg⁡u≥L+k+2(n−L−1).2(n-1)=\sum_u\deg u\ge L+k+2(n-L-1).
Simplifying the right side: 2n−L−2+k2n-L-2+k. Therefore 2n−2≥2n−L−2+k2n-2\ge2n-L-2+k, i.e. L≥kL\ge k.

Equality. It holds when all vertices other than vv and the leaves have degree exactly 22, that is when the tree is a "spider": paths glued at vv.

Lesson. Handshake lemma: relate the degrees to the number of edges.