# Graph Coloring : How to Think about Algorithms Exercise 1.6.2

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?

• 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.. Dec 6, 2017 at 16:11
• thanks I fixed it to "d" Dec 7, 2017 at 0:29
• You've got a typo in "each node has different color nodes".
– bof
Dec 7, 2017 at 0:40
• fixed : "each node has a different color" Dec 7, 2017 at 2:33

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.