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?


1 Answer 1


No, your reasoning is hard to find correct.

Induction is on the number of vertices, but not on $k$.

This is how it should be. The basis of induction $|V(G)|=1$.

Inductive step.

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .