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?

  • 1
    $\begingroup$ 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? $\endgroup$ – bof Dec 1 '17 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.

  • $\begingroup$ 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? $\endgroup$ – xdavidliu Dec 1 '17 at 4:14
  • $\begingroup$ @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.$ $\endgroup$ – bof Dec 1 '17 at 4:17
  • $\begingroup$ @xdavidliu So this proof by induction on $d$ works. Still, induction on the number of vertices is much more natural. $\endgroup$ – bof Dec 1 '17 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.