• Support PF! Buy your school textbooks, materials and every day products Here!

Can someone help me understand what this problem is asking?

  • Thread starter TrolliOlli
  • Start date
  • #1
13
0

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

Answers and Replies

  • #2
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
682
I first assumed it was saying the graph must have more than (n-1)/2 edges
The problem is asking about [itex]\begin{pmatrix}n-1\\2\end{pmatrix}[/itex], not [itex]\frac{n-1}2[/itex], 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 [itex]\begin{pmatrix}n-1\\2\end{pmatrix}[/itex] then that graph must necessarily be a connected graph.

Your job is to prove this statement.
 
  • #3
13
0
The problem is asking about [itex]\begin{pmatrix}n-1\\2\end{pmatrix}[/itex], not [itex]\frac{n-1}2[/itex], 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 [itex]\begin{pmatrix}n-1\\2\end{pmatrix}[/itex] 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 [itex]\begin{pmatrix}n-1\\2\end{pmatrix}[/itex] before.

What exactly does this mean?
 
  • #4
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
682
It's the binomial coefficient.
[tex]\binom n k =\frac{n!}{(n-k)!\,k!}[/tex]
Substituting nn-1, k → 2, and expanding yields
[tex]\binom {n-1} 2 =\frac{(n-1)!}{(n-3)!\,2!} = \frac{(n-1)(n-2)}2[/tex]
 
  • #5
13
0
It's the binomial coefficient.
[tex]\binom n k =\frac{n!}{(n-k)!\,k!}[/tex]
Substituting nn-1, k → 2, and expanding yields
[tex]\binom {n-1} 2 =\frac{(n-1)!}{(n-3)!\,2!} = \frac{(n-1)(n-2)}2[/tex]
Thank you so much! That's exactly what I needed.
 

Related Threads for: Can someone help me understand what this problem is asking?

Replies
7
Views
575
Replies
4
Views
973
Replies
4
Views
2K
Replies
9
Views
3K
Replies
15
Views
1K
  • Last Post
Replies
1
Views
2K
Top