The problem says:

Given an undirected simple graph G such that each node has at most d + 1 neighbors, color each node with one of d + 1 colors so that for each edge the two nodes have different colors.

Hint : don't think too hard. just color the nodes. what loop invariant do you need?

I was trying to solve this.. but quickly realized a complete graph of 4 vertices, whose vertices have at most 3 neighbors, cannot be colored with one of 3 colors so that each node has a different color.

I did some research and it seems like the book had a typo and it should have been "... each node has at most d neighbors, color each node with one of d + 1 colors... "

It is possible to find a graph with maximum degree of d + 1 that can be colored with d + 1 colors but this cannot be true for such graph, right?

Am I correct in assuming that the typo should be corrected like how I did so AND about the last remark?

  • $\begingroup$ In your correction of the supposed typo you haven't actually corrected anything.. What I don't get is why there isn't any restriction on the variable $d$. I mean, why say "at most $d+1$ neighbours" and not just "$d$ neighbours, for $d \geq 4$" or something like that.. $\endgroup$
    – Ilefen
    Dec 6, 2017 at 16:11
  • $\begingroup$ thanks I fixed it to "d" $\endgroup$
    – namesake22
    Dec 7, 2017 at 0:29
  • $\begingroup$ You've got a typo in "each node has different color nodes". $\endgroup$
    – bof
    Dec 7, 2017 at 0:40
  • $\begingroup$ fixed : "each node has a different color" $\endgroup$
    – namesake22
    Dec 7, 2017 at 2:33

1 Answer 1


Your correction to each node has at most $d$ neighbors is correct. I don't know what loop invariant you need. I would just say you color the nodes one by one in any order. At each step you have at most $d$ colors used for neighbors, so have at least one color available.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .