Prove it's a Tree

Question

If any graph with $n$-vertices that is both connected and acyclic must have $n-1$ edges, then how does one prove that any graph with $n$-vertices, $n-1$ edges, and is acyclic must be a tree?

Answer 1

We proceed by induction. Note that if $G(n,n-1)$ is acyclic, $G$ must have a vertex $v$ with degree $1$. Consider the new graph $G'=G -{v}-{e}$, where $e$ is the incident edge in $v$. So, $G'$ have $n-1$ vertices and $n-2$ edges, without cycles. Then, by induction hypotheses, $G'$ is a tree and we concluded that $G$ is a tree.

Answer 2

Let the graph contain a cycle made of vertices $V_0=\{v_1,v_2,\dots, v_m\}$. This cycle also contains $m$ edges connecting the vertices. Let the set of these edges be called $E_0$

1. If $m=n$, then the graph has at least $n$ edges.
2. If $m<n$, then there exists a vertex $u$ which is connected to one of the edges in $V_0$ Add that vertex to $V_0$ and the edge connecting the vertex to $V_0$ to $E_0$ to get $E_0$ and $E_1$. Continue doing this until you get $V_k$ and $E_k$ where $|V_k|=n$. Because $|E_i|=|V_i|$ for each $i$, this means that the graph contains at least $n$ edges.

Note: The second part is not a rigurous answer, but can be made such by induction.