- #1

TrolliOlli

- 13

- 0

## Homework Statement

This is a screenshot from our online textbook:

Edit: Replaced oversized screenshot replaced with content

http://i.imgur.com/h2QX2.png

**7.2.11**Prove that a graph with [itex]n[/itex] nodes and more than [itex]\begin{pmatrix}n-1 \\ 2\end{pmatrix}[/itex] edges is always connected.

I first assumed it was saying the graph must have more than (n-1)/2 edges, but I don't think this can be right as I've shown below:

If: 1 node has degree 0

Then: n-1 nodes must have more than (n-1)/2 total edges

this IS possible however as n-1 nodes can have a max of (n-1)(n-2)/2 edges

Since I'm trying to prove that this isn't possible, my only solution is that I'm reading the number of edges wrong.

Thoughts?

Last edited by a moderator: