Graph theory question- Is this correct?

  • Thread starter talolard
  • Start date
  • #1
125
0

Homework Statement


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]




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.
Proof:
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]
finished?
 

Answers and Replies

Related Threads on Graph theory question- Is this correct?

Replies
1
Views
625
  • Last Post
Replies
3
Views
874
  • Last Post
Replies
7
Views
705
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
3
Views
985
Top