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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
