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

coloringgraph theoryinductionproof-verification

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?

Best Answer

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.

Related Question