1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Can someone help me understand what this problem is asking?

  1. Aug 31, 2012 #1
    1. The problem statement, all variables and given/known data
    This is a screenshot from our online text book:
    Edit: Replaced oversized screenshot replaced with content
    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.

    Last edited by a moderator: Aug 31, 2012
  2. jcsd
  3. Aug 31, 2012 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
  4. Aug 31, 2012 #3
    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?
  5. Aug 31, 2012 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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]
  6. Aug 31, 2012 #5
    Thank you so much! That's exactly what I needed.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook