1
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – bradhd May 3 '14 at 20:15
  • $\begingroup$ I must be confusing something then. Hmm. $\endgroup$ – Vincent May 3 '14 at 20:15
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.