Graph theory question- Is this correct?

[talolard]

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

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?

 

[mighty2000]

Yes, your proof is correct. Let me provide a more formal proof for clarity:

Proof:
Assume G is a simple graph of maximal degree X. Let U be the set of nodes that do not span any vertices in G. We want to show that |U| ≥ n/(X+1).

First, we will show that |U| is minimized when G is X-regular, i.e. every node is connected to exactly X other nodes.

Assume that there exists a node v in G with degree d < X. Then there are n-1-d nodes that do not span any vertices with v. This is because each of these nodes can only be connected to at most d other nodes, leaving at least n-1-d nodes unconnected to v. Therefore, the minimum value of |U| is when every node in G has degree X.

Now, we will divide G into n/(X+1) subgraphs, each with X+1 nodes. Since G is X-regular, each subgraph will have exactly X edges. However, each subgraph can only have at most X-1 edges between its nodes. Therefore, at least one pair of nodes in each subgraph will not be connected by an edge. This means that for each subgraph, there is at least one node in U.

Since we have divided G into n/(X+1) subgraphs and each subgraph has at least one node in U, we have at least n/(X+1) nodes in U. Therefore, |U| ≥ n/(X+1).

Hence, we have proven that for any simple graph G of maximal degree X, |U| ≥ n/(X+1).