Exercise 966Combinatorics › Graph theoryL1Added 3 Nov 2026

Characterizations of trees

#tree#characterization#connected

Statement

Let $G$ be a graph with $n$ vertices. Show that the following are equivalent:
1. $G$ is a tree;
2. $G$ is connected and has $n-1$ edges;
3. $G$ is acyclic and has $n-1$ edges;
4. Between any two vertices there is a unique path.

Hint

For $2\Rightarrow3$ : if $G$ had a cycle, removing an edge would keep it connected but reduce edges below $n-1$ , contradicting the tree edge count.

Show solutionHide solution

Solution

$1\Rightarrow2$ : by definition of tree (connected acyclic) plus the previous result.

$2\Rightarrow3$ : suppose $G$ connected, $n-1$ edges, and has a cycle. Remove an edge of the cycle: still connected, $n-2$ edges. But a connected graph on $n$ vertices needs at least $n-1$ edges. Contradiction. So acyclic.

$3\Rightarrow4$ : acyclic means no repeated-vertex cycle, so paths between any two vertices, if they exist, are unique. Connected follows from "acyclic with $n-1$ edges".

$4\Rightarrow1$ : unique paths imply connected (paths exist) and acyclic (a cycle would give two paths).

Conclusion. The four are equivalent.

Characterizations of trees

Statement

Solution

More problems in Graph theory