- #1
talolard
- 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?