Europe divided into regions of 1 million people

It's four, I think. Here's my stab at explaining this: in order to color it with only three colors any places with more than 2 neighbors who form a connected circle around the main region must have an even number of neighbors. There are a some places with odd numbers, ex: essen, rur ; london, london; dikirnis, misr as-suflaha all have 5 neighbors surrounding them. Because the neighbors also border each other they have to alternate colors around the main region. With an even number of neighbors they alternate fine; but with an odd number you'd end up with the first and last colored region being next to each other and matching - so you need 4 colors.