- #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: