Q:

Graph Theory and Induction

A simple undirected graph is connected if there is a path between every pair of vertices in the graph. 
Prove: if H is an undirected simple connected graph with n vertices, then H has ≥ n − 1 edges. Use induction.
Teacher has a knack for giving practice problems that combine multiple concepts. I am at a complete loss as to how to even begin using induction to prove the above problem. Any help would be appreciated!

A:

Does the result hold for 2 vertices?  Ask yourself, how many edges does a connected graph with 2 vertices have?  Is it at least $n-1=2-1=1$?
Now, suppose you got yourself a connected graph on $n$ vertices where $n>2$.  Carefully remove a vertex which does not disconnect the graph (you must convince yourself, and the reader of your proof, that this is possible or use some theorem from your text/notes) say $G-v$ is connected.  $G-v$ has one less vertex, so by induction it has at least $(n-1)-1$ edges.  Add $v$ back in along with all those edges incident to $v$ (What's the smallest number of edges added back in at this step?).  Now, count (get a lower bound) on the number of edges in $G$.  Hopefully, the number of edges is at least $n-1$.  

