How is the graph coloring problem NP-Complete?

For a check, you are given with a particular coloring of the given map. You just go through all the patches, check that the neighbors are of different color, and finally count the total number of colors. This algorithm scales linearly with the number of regions, so it is a polynomial check.

UPDATE: For a general graph (not necessarily planar) this algorithm will be at most quadratic in the number of vertices (colored regions).

The Graph Coloring decision problem is np-complete, i.e, asking for existence of a coloring with less than 'q' colors, as given a coloring , it can be easily checked in polynomial time, whether or not it uses less than 'q' colors.

On the other hand the Graph Coloring Optimisation problem, which aims to find the coloring with minimum colors is np-hard, because even if you are given a coloring, you will not be able to say that it's minimum or not. This is the basic difference b/w np-complete and np-hard, and is applicable to many other problems as well, such as the Travelling Salesman Problem.