# How would you prove that a graph $G = (V, E)$ is a tree?

How would you prove that a graph $G = (V, E)$ that has no cycles and contains $|V| - 1$ edges must be a tree?

Definition used for a tree: $A$ graph is a tree if it is connected and has no cycles and a simple cycle is formed if any edge is added to $G$, but is not connected if any single edge is removed from $G$.

• What definition of tree are you using? – Michael Biro Mar 24 '13 at 23:01
• A graph is a tree if it is connected and has no cycles and a simple cycle is formed if any edge is added to G, but is not connected if any single edge is removed from G. But i can't figure out how it is related? – jack Mar 24 '13 at 23:04

Can you show that a graph with no cycles and $|V|-1$ edges must be connected?
Once you do that, show that adding an edge closes a cycle (since $G$ is connected, there is already a path connecting the two vertices). Then show that removing an edge disconnects the graph (as otherwise there would have been a cycle).
• Use induction on $|V|$. The base case is easy, so assume that any graph with $|V| < n$, no cycles and $|V| - 1$ edges is connected. Take any graph $G$ with $n$ vertices, no cycles and $n - 1$ edges. Pick an edge $e = (u,v)$ and condense $G$ by replacing vertices $u$ and $v$ with vertex $uv$, and replacing any edge $(u,x)$ or $(v,x)$ with $(uv,x)$. The resulting graph $G^\prime$ is still simple, has no cycles, and has $n-1$ vertices with $n-2$ edges, so by induction it is connected. We can easily convert paths in $G^\prime$ into paths in $G$, so $G$ is connected. – Michael Biro Mar 26 '13 at 6:45