[Math] Prove that a $k$-degenerate graph is ($k+1$)-colorable

Question

A graph is $k$-degenerate if every induced subgraph contains a vertex of degree at most $k$. How can I prove that a $k$-degenerate graph is ($k+1$)-colorable?

Answer 1

Hints: If $G$ is the given $k$-degenerate graph, notice that $G$ is an induced subgraph of itself and so $G$ has a vertex $v$ of degree at most $k$.

Why is $G-v$ also $k$-degenerate?

Now apply induction on the number of vertices to colour $G- v$ with $k+1$ colours.

Can you now colour $v$ with one of the $k+1$ colours to obtain a proper $k+1$-colouring of $G$?