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?