Q:

Proving graph theory using induction

How would I go about proving that a graph with no cycles and n-1 edges (where n would be the number of vertices) is a tree?
I am just really confused about where to start.
Thanks in advance. 

A:

First check for $n=1$, $n=2$. These are trivial. Assume it is true for $n = m$. Now consider $n=m+1$. The graph has $m+1$ vertices with $m$ edges and no cycles. Now by handshake lemma, there exists at least $2$ vertices with degree $1$. Pick on such vertex and remove it from the graph. Now you have graph on $m$ vertices with $m-1$ edges, which is a tree by induction assumption. Now complete.

