Can someone help me understand what this problem is asking?

[TrolliOlli]

Homework Statement

This is a screenshot from our online textbook:
Edit: Replaced oversized screenshot replaced with content[/color]
http://i.imgur.com/h2QX2.png
7.2.11 Prove that a graph with n nodes and more than \begin{pmatrix}n-1 \\ 2\end{pmatrix} 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?

 

[D H]

I first assumed it was saying the graph must have more than (n-1)/2 edges

The problem is asking about \begin{pmatrix}n-1\\2\end{pmatrix}, not \frac{n-1}2, and it doesn't say that a graph must have more than that many edges. What it says is that if a graph of n nodes does have more than \begin{pmatrix}n-1\\2\end{pmatrix} then that graph must necessarily be a connected graph.

Your job is to prove this statement.

 

[TrolliOlli]

The problem is asking about \begin{pmatrix}n-1\\2\end{pmatrix}, not \frac{n-1}2, and it doesn't say that a graph must have more than that many edges. What it says is that if a graph of n nodes does have more than \begin{pmatrix}n-1\\2\end{pmatrix} then that graph must necessarily be a connected graph.

Your job is to prove this statement.

Thank you very much for the clarification. I'm guessing however that I must have missed something as I've never seen something of the form \begin{pmatrix}n-1\\2\end{pmatrix} before.

What exactly does this mean?

 

[D H]

It's the binomial coefficient.
\binom n k =\frac{n!}{(n-k)!\,k!}
Substituting n → n-1, k → 2, and expanding yields
\binom {n-1} 2 =\frac{(n-1)!}{(n-3)!\,2!} = \frac{(n-1)(n-2)}2

 

[TrolliOlli]

It's the binomial coefficient.
\binom n k =\frac{n!}{(n-k)!\,k!}
Substituting n → n-1, k → 2, and expanding yields
\binom {n-1} 2 =\frac{(n-1)!}{(n-3)!\,2!} = \frac{(n-1)(n-2)}2

Thank you so much! That's exactly what I needed.