prove that a connected graph with $n$ vertices has at least $n-1$ edges
A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.
Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds. If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.
There are two standard approaches:
Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).
Induction on the size of the graph. Assume you have a connected graph of $n$ vertices and $m$ edges. Remove the edges until your graph splits in two parts. By inductive hypothesis both parts have at least $n_1 - 1$ and $n_2 - 1$ edges (where $n_1+n_2 = n$), so your graph had at least $n_1 -1 + n_2 - 1 + 1 = n - 1$ edges (the additional one denotes the last edge you removed before the graph stopped being connected).
I hope this helps $\ddot\smile$
Let $V = \{v_1, v_2, \dots, v_n\}$ be the set of vertices and consider the $n \times (n-1)$ triangle
$$ \begin{eqnarray} (v_1, v_2) & (v_1,v_3) & \cdots & (v_1, v_n) \\ & (v_2, v_3) & \cdots & (v_2,v_n) \\ & & & \; \; \; \; \vdots \\ & & & (v_{n-1}, v_n) \end{eqnarray}$$ where each point is associated with a potential edge. Circle an entry, say, if the graph does have an edge. If there are strictly less than $n-1$ edges, because there are $n-1$ rows there must be one of them without any edges. But a row is of the form $(v_i, v_j)$, $i<j$, and there being no edges on it means $v_i$ is not connected. But this means the graph isn't connected. So there are at least $n-1$ edges.