# Can someone help me understand what this problem is asking?

## Homework Statement

This is a screenshot from our online text book:
Edit: Replaced oversized screenshot replaced with content
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?

Last edited by a moderator:

D H
Staff Emeritus
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.

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
Staff Emeritus
It's the binomial coefficient.
$$\binom n k =\frac{n!}{(n-k)!\,k!}$$
Substituting nn-1, k → 2, and expanding yields
$$\binom {n-1} 2 =\frac{(n-1)!}{(n-3)!\,2!} = \frac{(n-1)(n-2)}2$$

It's the binomial coefficient.
$$\binom n k =\frac{n!}{(n-k)!\,k!}$$
Substituting nn-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.