I think the example is fine. Two adjacent regions will indeed always be different if the coloring is correct. But it may not be if the coloring is incorrect.