I don't understand why the Costa Rica example is 3-colorable. The green province in the middle touches 5 other provinces so it seems like it should be 5-colorable.
Consider a pizza sliced into six pieces. Each piece touches only their neighbor on each side, so you can color them alternately red and blue. Now suppose someone carved an island in the middle around an olive that no one wants. That touches all six, but can still be colored green, so we use only three colors in total, despite the middle "region" having six neighbors.