I think strong induction might be the best approach here, to avoid having to find a non-cut vertex (a vertex that, when removed along with its incident edges, does not disconnect the graph). Induction proofs require a family of propositions $P(n)$, indexed by natural numbers $n$. I usually find it easier to explicitly define it:
$P(n) :$ For all connected graph $G$ with $n$ vertices, $G$ has at least $n - 1$ edges.
We need to prove $P(1)$ first. That is, if $G$ is a connected graph with $1$ vertex, then $G$ has at least $0$ edges. This is clear of any graph, not just connected ones with $1$ vertex, so $P(1)$ is true.
We suppose now that, for a fixed $n > 1$, $P(k)$ is true for all $k < n$, and proceed to prove $P(n)$. We need to show that, given any connected $G$ graph with $n$ vertices, we have at least $n - 1$ edges, so let's suppose that we have some graph $G$ fitting these premises.
Take any vertex $v$ of $G$, delete it, along with all of its incident edges, to form a new graph $G'$. Note that $v$ cannot have zero degree, because then it would not be connected to the rest of the graph. We cannot assume $G'$ is connected (which would be handy, so that we could apply $P(n - 1)$), but what we can do is consider the connected components of $G'$. Let $G_1, G_2, \ldots, G_m$ be the number of connected components of $G$. For each $i = 1, \ldots, m$, let $n_i$ and $e_i$ be the number of vertices and edges respectively of $G_i$.
Note that $G'$ has $n - 1 = n_1 + \ldots + n_m$ vertices and $e_1 + \ldots + e_n$ edges. In particular, $n_i < n$ for all $i = 1, \ldots, m$. We can therefore use our induction hypothesis, and conclude that $P(n_i)$ is true for all $i$. That is, $e_i \ge n_i - 1$. Summing up, we get,
$$n - 1 = n_1 + \ldots + n_m = (n_1 - 1) + \ldots + (n_m - 1) + m \le e_1 + \ldots + e_m + m$$
Since removing $v$ created $m$ connected components, it follows that $v$ must have had at least $m$ edges incident to it (at least one edge must have connected to each connected component of $G'$ to connect them all in $G$). Thus, if $e$ is the number of edges in $G$, we have
$$n - 1 \le e_1 + \ldots + e_m + m \le e,$$
as required. Thus, by (strong) induction, $P(n)$ holds for all $n$.