1. Not finding help here? Sign up for a free 30min 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!

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
    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: 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook