fewest colors d+1 needed to color graph with some maximal degree d, inducting on d rather than number of vertices

Question

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."

This problem was discussed in a past thread here, as well as another thread.

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?

Answer 1

It is not valid. Note that two vertices with degree $d$ can be adjacent in the original graph. If you color both of them by the $(d + 1)$-th color, it is not a valid coloring.

---

Instead of removing all vertices with degree $d$ at once, remove vertices one by one as follows:

1. if there is a vertex $v$ with degree $d$, remove $v$ and decrease the degrees of $v$'s neighbors by $1$;
2. repeat step 1 until no such $v$ exists;

Since $d$ is the maximum degree, in this way, it is guaranteed that

• the vertices removed are not adjacent to each other; and

• the maximum degree of the graph remained is at most $d - 1$.

Then, by your assumption, the graph remained can be colored by $d$ colors. We can color the vertices removed by the $(d + 1)$-th color.