There may be a more clever way to do this, but the simplest way seems to be induction on the number of vertices of the graph.
So, let k be the maximum degree of a vertex of G. The least number of vertices that such a graph can have is k+1, and in this case G is easily seen to be (k+1)-colorable (just color each vertex a different color).
Now let G be such a graph on n > k+1 vertices, and let v be a vertex of G of maximal degree (i.e., deg(v) = k). If every vertex of G is a neighbor of v, then we're back in the base case. Thus, we can assume that there is some vertex w of G that is not a neighbor of v. Then G - w is a graph on n-1 vertices whose maximum degree is k. Thus, by induction, there is a coloring of G - w using k+1 colors. Use this coloring to color all the vertices of G except w. Since w has < k+1 neighbors and our coloring used k+1 colors, there must be some color not appearing among the neighbors of w. Color w with this color to extend the coloring to all of G.
Answers & Comments
Verified answer
There may be a more clever way to do this, but the simplest way seems to be induction on the number of vertices of the graph.
So, let k be the maximum degree of a vertex of G. The least number of vertices that such a graph can have is k+1, and in this case G is easily seen to be (k+1)-colorable (just color each vertex a different color).
Now let G be such a graph on n > k+1 vertices, and let v be a vertex of G of maximal degree (i.e., deg(v) = k). If every vertex of G is a neighbor of v, then we're back in the base case. Thus, we can assume that there is some vertex w of G that is not a neighbor of v. Then G - w is a graph on n-1 vertices whose maximum degree is k. Thus, by induction, there is a coloring of G - w using k+1 colors. Use this coloring to color all the vertices of G except w. Since w has < k+1 neighbors and our coloring used k+1 colors, there must be some color not appearing among the neighbors of w. Color w with this color to extend the coloring to all of G.
QED