# Graph theory question- Is this correct?

1. Jun 14, 2010

### talolard

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 $$|U| \geq \frac{n}{X+1}$$

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.
Proof:
Let v be some node in G such that the $$degr(v)=y < X$$. Then there are $$n-1-y$$ nodes so that there are no vertices between those nodes and v.

Assume that G is X-regular. Then if we divide G into$$\frac{n}{X+1}$$ 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 $$|U| \geq 1 \frac{n}{X+1}$$
finished?