# Show that every k-degenerate graph has chromatic number at most k+1

Saw on Wikipedia that: "A k-degenerate graph has chromatic number at most k + 1; this is proved by a simple induction on the number of vertices which is exactly like the proof of the six-color theorem for planar graphs". Wondering what the explicit proof of this by induction is. What I have so far is that if I have a graph G for this being true. Then by induction my base case of 1 vertex this is obviously true since this has deg 0 and can be easily colored by $$k$$ colors. But then for the inductive step if I have a Graph where a vertex has a vertex of deg $$k+1$$ and we have $$k+2$$ colors, then I can delete the vertex $$v$$ which has deg $$k+1$$ and I know by our inductive hypothesis this can be colored by $$k+2$$ colors. I know adding it back that it can be colored since we have $$k+2$$ colors and with $$k+1$$ edges leading in it is obvious that we can trivially color it to have a valid coloring of our graph. Is this a valid proof?

Induction is on the number of vertices, but not on $$k$$.
This is how it should be. The basis of induction $$|V(G)|=1$$.
Let $$G$$ be a $$k$$-degenerate graph and $$|V(G)|>1$$. Let $$v\in V(G)$$ be a vertex of degree $$k$$. Consider the graph $$H=G-v$$. Since $$H$$ is a subgraph of graph $$G$$, then $$H$$ is also a $$k$$-degenerate graph (or $$k'$$-degenerate with $$k'\leq k$$). By induction, graph $$H$$ can be colored in $$k+1$$ colors. Now we return the vertex $$v$$, its neighbors are colored in no more than $$k$$ colors, so $$v$$ can be colored in one of $$k+1$$ colors.