# 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. Jun 15, 2014 at 12:40
• An interesting corollary of this statement is that for a connected graph $G = (V,E)$ on $n$ vertices, a forest $E’ \subseteq E$ is a spanning tree of $G$ if and only if $E'$ has $n-1$ edges. Feb 2 at 10:56

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.
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.