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

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?

• What if all vertices have the same degree $d$? "take all such vertices and remove them, and we will be left with . . ." nothing. How is your inductive hypothesis going to help you in that case?
– bof
Dec 1, 2017 at 4:15

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.

• this method implies that it doesn't matter which degree-$d$ vertices we initially choose to remove; it will all work in the end. How are we certain that using this method will not remove two vertices that were initially next to each other? Dec 1, 2017 at 4:14
• @xdavidliu Because, if two vertices of degree $d$ are initially next to each other, then as soon as you remove one of them, the degree of the other drops to $d-1.$
– bof
Dec 1, 2017 at 4:17
• @xdavidliu So this proof by induction on $d$ works. Still, induction on the number of vertices is much more natural.
– bof
Dec 1, 2017 at 4:17