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:

1. Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).

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