Prove or disprove bound on chromatic number.

Solution 1:

Hint: I would start the same way you did; assume that $\chi(G)>|D|$. This means there are at most $\chi(G)-1$ vertices with degree at least $\chi(G)-1$. We will get a contradiction by showing how to color $G$ using only $\chi(G)-1$ colors, contradicting the definition of the chromatic number.

The idea is this; start by coloring the vertices of $D$ with $\chi(G)-1$ distinct colors, which is possible since $|D|\le \chi(G)-1$. Then, color the rest of the graph one vertex at a time, choosing, for each vertex, a color not present among its previously colored neighbors. Since every vertex not in $D$ has degree at most $\chi(G)-2$, and there are $\chi(G)-1$ colors available, there will always be at least one color not present in each vertex's neighbors. Therefore, you can color the rest of the graph. Contradiction!