Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory question- Is this correct?

  1. Jun 14, 2010 #1
    1. The problem statement, all variables and given/known data
    For any simple Graph G of maximal degree X, let U be the set of nodes that do not span any vertice in G. prove that [tex] |U| \geq \frac{n}{X+1} [/tex]

    3. The attempt at a solution
    First we notice that |U| is minimized when G is X-regular, i.e. that every node is connected to exactly X other nodes.
    Let v be some node in G such that the [tex]degr(v)=y < X [/tex]. Then there are [tex] n-1-y [/tex] nodes so that there are no vertices between those nodes and v.

    Assume that G is X-regular. Then if we divide G into[tex] \frac{n}{X+1} [/tex] subgraphs, in any fashion, there will be at least one pair of nodes with no vertices between them. This is because each subgraph will have at least X+1 nodes but each node is of maximal degree X. And since each such division "contributes" at least 1 such pair we have that [tex] |U| \geq 1 \frac{n}{X+1} [/tex]
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?