and the United States with the state of Alaska. If we require the entire territory of a country to receive the same color, then four colors are not always sufficient. For instance, consider the simplified map:

In this map, the two regions labeled A belong to the same country. If we want those regions to receive the same color, then five colors are required, since the two A regions together are adjacent to four other regions, each of which is adjacent to every other.