[Vicomte13]

How can the article say "Four Colors"?

Russia touches at least 10 other countries. If you only used four colors, you would have to have the same color touching at least thrice.

I suppose if you just limited the scope to "map of Europe", but even then, you'd have to leave out the Balkans to use just four colors.

If a computer can "prove" that only four colors are needed, then the computer is clearly in error.

[Our man in washington]

Think again.

You could use the same color for Finland, Poland and China, as they don't border each other.

[LexBaird]

Russia touches at least 10 other countries. If you only used four colors, you would have to have the same color touching at least thrice.

Yes, but those 10 (may be more than that now...) don't all touch each other. Thus, Russia is color 1, and all the others touching it are 2, 3, or 4.

[1L]

You didn't read it clearly: all that's required is that Russia be a different color than any color touching it, not that all countries touching it be a different color, unless they themselves touch. So, Mongolia and Finland can be the same color.

[jwalsh07]

If a computer can "prove" that only four colors are needed, then the computer is clearly in error.

Computer is OK as long as all countires are contiguous. Since they aren't you are right, the computer is in error when talking about maps of the world.

[kevkrom]

Several people have pointed out why four is sufficient for Russia. My only comment on the "four colors" solution is that is limited to the practical example of existing maps. If by being "adjacent" requires only a single point of intersection on the border, than I can create abstract examples of any size N to show that N colors are insufficient:

Starting with N = 4... Picture a "four corners" scenario like the states in the US Southwest. No problem... even though they all intersect at a single point, you have four colors. However, if you add one region/state/whatever that surrounds all four (or also intersects at the same point), the you would need a fifth color. Repeat as necessary for every N + 1.

The problem is only solvable for N = 4 if "adjacent" requires more than one point of border intersection.