Identifying a Tree by Edge Count

Recall the characterization of trees in terms of connectivity and edge count.

A connected graph with exactly n-1 edges cannot contain a cycle.

1. 1. Rule out cycles

   If a connected graph on $n$ vertices with $n-1$ edges contained a cycle, removing one edge from that cycle would keep it connected with only $n-2$ edges, which is too few to connect $n$ vertices (a connected graph needs at least $n-1$ edges), a contradiction.

2. 2. Conclude it is a tree

   A connected graph with no cycles and exactly $n-1$ edges is, by definition, a tree.

Answer: A tree.