I was working on the following proof problem:
"Suppose you have an undirected graph with maximal degree (e.g. number of edges from a single vertex) $d$, and you want to color all the vertices so that none of the edges (immediately) connect two vertices of the same color. Prove this can always be done with $d+1$ different colors."
In both those threads, the proofs presented are inductive, and iterates on the number of vertices $n$ of the graph, while keeping the maximal degree $d$ fixed. The proofs are correct, and I have no issue with them.
However, I thought that it seems more natural to iterate on $d$, rather than $n$, because the theorem focuses on $d$. For example, here's a sketch of a proof that I thought of:
- Suppose the theorem is true for all undirected graphs of maximal degree $d-1$, e.g. all such graphs can be colored with $d$ colors.
- Then, suppose we have a graph with maximal degree $d$. This means there is at least one vertex with $d$ edges touching it.
- Take all such vertices and remove them, and we will will be left with a graph of maximal degree $d-1$, and this remaining graph can be colored with $d$ colors, as we initially assumed
- Now take the vertices that we removed, paint them a $d+1$th color, and then put them back in the original graph with their edges. Hence, we have a maximal-degree $d$ graph that can be colored with $d+1$ colors.
This proof seems conceptually more natural than the ones presented in the previous threads, so I'm wondering if this proof is valid?