prove that a connected graph with $n$ vertices has at least $n-1$ edges Show that every connected graph with $n$ vertices has at least $n − 1$ edges.
How can I prove this?  Conceptually, I understand that the following graph has 3 vertices, and two edges:
a-----b-----c
with $a$, $b$ and $c$ being vertices, and $\{a,b\}$, $\{b,c\}$ being edges.
Is there some way to prove this logically?
--UPDATE--
Does this look correct?  Any advice on how to improve this proof would be appreciated.  Thank you.

 A: 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$
A: 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.
A: Let G be a connected Graph :
If G has no cycles then G  is connected with no cycles $=> G$ is a Tree.
So $G$ has n-1 edges. 
If G has cycles : and  $G $ is connected then for every two vertices there is a path between them.
Assuming that $G$  have only  one cycle:
lets look at the path : $ v_1,v_2 \dots v_n,v_1 $ we can remove the edge $ v_1,v_1$ and we will get a connected  sub Graph  $ v_1,v_2$ with no cycles and $E(H)+1 =E(G)$ so $E(G)=n$.
And by induction  you will get that for every number of cycles n  $E(G)\ge n$.
So if $G $ has cycles  $E(G)=n-1$ else  $E(G)\ge n$ .
A: 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.
A: This result is immediate by induction once you have established (as lemma) that in every connected graph with at least two vertices there are at least two vertices that can be individually removed (with all adjacent edges) such that the remaining graph is still connected. (The inductive proof applies removal of such a vertex.) The lemma itself in turn is proved by a fairly easy induction on the number of vertices.
A: Hint: Let $\Gamma$ be a connected graph. If $T \subset \Gamma$ is a maximal subtree, then $|E(\Gamma)| \geq |E(T)|$ and $|V(\Gamma)|=|V(T)|$. (Where $E(\cdot)$ and $V(\cdot)$ is the set of edges and vertices respectively.)
A: Consider any arbitrary vertex of the n vertices, call it vertex A. Since the graph is connected, there always exists atleast one simple path(without cycles) from vertex A to all vertices (excluding A). Now for consider two simple paths from A to B and A to C. If B is not same as C, there must be atleast one edge which is different in the two paths. Since atleast n-1(since n-1 vertices excluding A are present) paths exist, n-1 edges are must
A: We can use Disjoint Sets here. Disjoint Set Data Structure aka Union-Find Data Structure is quite popular in Computer Science (Cycle Detection etc.).
Disjoint Sets of Vertices are very handy in defining connected components in a graph. The number of Disjoint Sets (DS) equals the number of connected components. $v,u \in V$ are members of same DS if there is a path from $u$ to $v$.
To construct DSs of a graph, we start with $|V|$ Sets with each $v\in V$ representing a DS. Then we add the edges information. For each $\{v,u\} \in E$, we find the DSs to which $v$ and $u$ belong and union the two sets if they lie in different DSs. So for each edge, there is either $1$ or $0$ union operation.
In this setting, since the graph is connected, we must have a single DS at the end. To merge $|V|$ DSs to one, we must have $|V|-1$ Union operations. Hence at least $|V|-1$ edges are required.
Generalisation :
If a graph has $k$ connected components, we must have $|V|-k$ union operations. Hence, $|E| \geq |V|-k$ or $|E|+k \geq |V|$
