# Graph Coloring Problem : How to Think About Algorithms Exer 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 different color nodes.

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 any graph with max degree of d + 1, right?

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

You're right that the statement is false. The correct statement states that every undirected simple graph in which each node has at most $d$ neighbors can be colored using $d+1$ colors so that each edge connects nodes having different color. Stated in more idiomatic language, every undirected simple graph of maximum degree $d$ can be (properly) colored using $d+1$ colors.