Can someone help me understand what this problem is asking?

  • Thread starter TrolliOlli
  • Start date
In summary, the conversation is about proving that a graph with n nodes and more than \begin{pmatrix}n-1\\2\end{pmatrix} edges is always connected. The participant initially misunderstood the problem but was later clarified that the statement is asking to prove that if a graph of n nodes has more than \begin{pmatrix}n-1\\2\end{pmatrix} edges, it must be a connected graph. The notation \begin{pmatrix}n-1\\2\end{pmatrix} represents the binomial coefficient and can be expanded to \frac{(n-1)(n-2)}{2}.
  • #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:
Physics news on Phys.org
  • #2
TrolliOlli said:
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
D H said:
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
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
D H said:
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.
 

1. What are the key terms or concepts in the problem?

The first step in understanding a problem is to identify the key terms or concepts. These are the words or phrases that are essential to understanding the problem and solving it. Make sure to define and clarify any terms that are unfamiliar.

2. What is the main objective or goal of the problem?

Understanding the main objective or goal of the problem is crucial in finding a solution. This will help guide your thinking and determine the appropriate approach to take in solving the problem.

3. What are the given information and what are you trying to find?

It's important to clearly identify the given information in the problem and what you are trying to find. This will help you organize your thoughts and determine what steps you need to take in order to solve the problem.

4. Are there any specific formulas or equations that can help solve the problem?

Some problems may require the use of specific formulas or equations in order to be solved. Make sure to carefully read the problem and see if there are any relevant formulas or equations that can be applied.

5. Can you break down the problem into smaller, more manageable parts?

Some problems may seem overwhelming at first, but breaking them down into smaller, more manageable parts can make them easier to understand and solve. Try to identify any smaller problems within the larger problem and tackle them one at a time.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
981
  • General Math
Replies
8
Views
984
Replies
23
Views
1K
  • Programming and Computer Science
Replies
3
Views
635
  • Electrical Engineering
Replies
5
Views
924
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
32
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
Back
Top