Exercise 474Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

Leaves of a tree

#tree#leaves#degree

Statement

Show that every tree with at least $2$ vertices has at least $2$ leaves (vertices of degree $1$ ).

Hint

Take a longest path in the tree. Its endpoints have degree $1$ .

Show solutionHide solution

Solution

Longest path. Let $P=v_0$ - $v_1$ - $\cdots$ - $v_k$ be a longest path.

Degree of endpoints. If $v_0$ had another neighbor $u$ , then $u$ - $v_0$ - $v_1$ - $\cdots$ - $v_k$ would be a longer path (if $u$ is not already on the path) — contradiction. Similarly for $v_k$ .

Conclusion. $v_0$ and $v_k$ are leaves (degree $1$ ), so there are at least $2$ leaves.

Leaves of a tree

Statement

Solution

More problems in Graph theory