how to prove that any graph with vertex coloring number $x$ must contain at least $x$ vertices of degree $\geq$ $x-1$ part a required using Brooks' theorem and now I'm trying to solve this by showing an example where a graph with coloring number $x$ does not contain degree $\geq$ $x-1$ and that some colors occurs at vertices of $\leq$ $x-2$. Not sure how to show that this color can be eliminated.
 A: Suppose the coloring number of a graph $G$ is $x$. Let $W$ be the set of vertices of $G$ whose degree is at least $x-1$.  We need to show $|W| \ge x$. 
By way of contradiction, suppose $|W| \le x-1$.  One way to color $G$ using a small number of colors is to first assign the smallest possible integer (color) to each vertex in $W$ and then to color the remaining vertices $V(G)-W$.  This ordering of the vertices for the greedy algorithm is such that vertices of large degree are colored first, so that the vertices being colored later have fewer neighbors which have already been assigned colors. 
If we color the vertices of $G$ in the order mentioned above, then each vertex in $W$ can be assigned a color from $\{1,2,\ldots,x-1\}$ because $W$ has at most $x-1$ vertices. Since each vertex in $V(G)-W$ has degree at most $x-2$, these vertices can also be assigned a color from $\{1,2,\ldots,x-1\}$. But this means $G$ can be colored using $x-1$ colors, a contradiction.
A: Try using greedy coloring. Which vertices are most likely to get you into trouble by running out of available colors? Those are the vertices you'd want to color greedily first.
