Exercise 473Combinatorics › Graph theoryHigh schoolAdded 3 Nov 2026

Trees

#tree#connected acyclic#edges

Statement

Show that a tree with $n$ vertices has exactly $n-1$ edges.

Hint

Induction on $n$ : a tree has a leaf; remove it and apply the induction hypothesis.

Show solutionHide solution

Solution

Base. $n=1$ : $0$ edges $=n-1$ .

Inductive step. A tree with $n\ge2$ has a leaf $v$ (a vertex of degree $1$ ; otherwise a longest path would give a cycle). Remove $v$ and its edge: the result is a tree with $n-1$ vertices, hence $n-2$ edges by induction. So the original tree has $n-1$ edges.

Conclusion. $|E|=|V|-1$ for every tree.

Trees

Statement

Solution

More problems in Graph theory