A Graph $G$ is $k$-degenerate if every Subgraph $H \subset G$ has at least one Vertex with degree $\leq k$. I know how to easily show that these graphs are $5$-colourable via induction. Since $G$ is a subgraph of $G$ we have a vertex with degree at most $4$. Call this vertex $v$. Using the induction hypothesis on $G-v$ and adding $v$ back gives us the $5$-colourability. However, I do not know how to prove that these graphs are indeed $4$-colourable.
Furthermore, I have the question if the complete Graph $K_5$ is a $4$-degenerate graph, because there is no vertex with degree higher than $4$. However, this would result in an contradiction, would not it?
Thanks for your help.
Best Answer
Every $k$-degenerate graph is $k+1$-colourable, and this is best possible, as the complete graph $K_{k+1}$ shows. In other words, your reasoning is correct, and whoever told you that every $4$-degenerate graph is $4$-colourable was wrong. Is this an exercise in a book?