The four color theorem states that any map with connected countries each country can be colored one of four colors so that no two countries that share a boarder are the same color. What happens if the countries do not need to be connected?

(a) Show that if the countries can be arbitrary disconnected sets that an unlimited number of colors may be necessary.

(b) Show that if each country can have at most 2 disconnected regions that 12 colors is sufficient. Hint: Show that the relevant graph has minumum degree at most 11.

(c) Give an example of a map where each country has at most 2 disconnected regions for which 9 or more colors are required.