# Show that a connected graph on $n$ vertices is a tree if and only if it has $n-1$ edges.

Show that a connected graph on $n$ vertices is a tree if and only if it has $n-1$ edges.

$(\Rightarrow)$ If a tree $G$ has only $1$ vertex, it has $0$ edges. Now, assume that any tree with $k-1$ vertices has $k-2$ edges. Let $T$ be a tree with $k$ vertices. Remove a leaf $l$ to obtain a tree $T'$ with $k-1$ vertices. Then, $T'$ has $k-2$ edges, by the inductive hypothesis. The addition of $l$ to $T'$ produces a graph with $k-1$ edges, since $l$ has degree $1$.

$(\Leftarrow)$ Let $G$ be a connected graph on $n$ vertices, with $n-1$ edges. Suppose $G$ is not a tree. Then, there exists at least one cycle in $G$. Successively remove edges from cycles in $G$ to obtain a graph $G'$ with no cycles. Then, $G'$ is connected and has no cycles. Therefore, $G'$ is a tree, with $n$ vertices and $n-1-x$ edges, for some $x > 0$. However, this contradicts the previous derivation. Therefore, it must be the case that $G$ is a tree.

• it seems to be true. – mesel Jun 15 '14 at 12:40

The proofs are correct. Here's alternative proof that a connected graph with n vertices and n-1 edges must be a tree modified from yours but without having to rely on the first derivation:

Let $G$ be a connected graph on n vertices, with n−1 edges. Suppose $G$ is not a tree. Then, there exists at least one cycle in $G$. Remove one of the edges within a cycle. This leaves a connected graph on n vertices with n-2 edges which is impossible as a connected graph on n vertices must at least have n - 1 edges.

Yes, this seems like it is true, although you didn't prove a leaf must always exist, if you really want to be rigorous. And in the other part you didn't explain why if it contained a cycle you could remove an edge without the graph being disconnected, but I like the proof over all.

I have the following way of proving it. Let me know if you agree with it or not.

Suppose the graph on $n$ vertices with $n-1$ edges is not a tree. This implies it has at least $1$ polygon. Suppose in total there are $k$ edges involved in these polygons and we know that a polygon has as many edges as vertices, since polygons are of regular degree 2. Then, if we consider th egraph without the edges that form the polygons, then we have a connected graph with at least $n-k$ edges, since in a connected graph every vertex has degree at least 1. Thus, in total this would imply we have at least $n$ in all the graph. But this contradicts the fact that we have $n-1$ in the original graph. Thus it must be a tree.

The converse is not always true. Consider a disjoint graph with n vertices and n - 1 edges. Here we have n-1 edges but this is obviously not a tree. The assumption that G is connected is only for the forward implication.