# 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

## 2 Answers

Adding an edge to a graph can connect at most two connected components.

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.

• I think this proof has far too much handwaving for this level. Which edges? How do you know they are distinct? – Erick Wong May 3 '14 at 20:24