Prove that a graph with $n$ vertices and less than $n$-1 edges, is disconnected.

Prove that if $G$ is a graph with $n$ vertices and fewer than $n$-1 edges, then $G$ is disconnected.

The book I am working through uses a similar definition of "$n$ vertices and at least $n$-1 edges, then $G$ is connected". They do not provide a proof for that, and now it is asking for the proof of 'fewer than $n$-1 edges, then $G$ is disconnected. I'm not sure how to go about this proof. Any help would be great!

• It's not true that every graph with $n$ vertices and at least $n-1$ edges is connected: consider the graph with two components, both of which are triangles. This has $6$ vertices and $6$ edges, but is not connected. – bradhd May 3 '14 at 20:15
• I must be confusing something then. Hmm. – Vincent May 3 '14 at 20:15

Since the empty graph starts with $n$ connected components, adding less than $n-1$ edges will not get you down to a single connected component.
Pick a vertex. To go to the other $n-1$ vertices from our chosen vertex requires at least $n-1$ distinct edges. Then the conclusion follows.