There seems to be a problem with the article: the example shown is with colouring the map. But showing two adjacent regions to have different colours proves nothing: they will always be different (if colouring is possible). Perhaps if one shows two regions that do not share a border, and state that they are or are not the same colour...
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.