Four-Color Problem - Part I

Preliminary:

• The four-color conjecture states that any map can be colored with four colors so that no two adjacent countries have the same color.


• It can be shown that any map can be converted to a so-called cubic map where each node terminates three edges without loss of generality.
  
• If maps exist that are not four-colorable, then one such map must be of minimum size.
  It follows that a minimum map with one country (face) removed is four colorable.


• A minimal map cannot contain a face with only one, two, or three edges for if that map with that face removed is colored there has to be at least one color left to color that face.


• A minimal map cannot contain a face with four edges: Suppose we have such a face surrounded by colors a opposite to c and b opposite to d. (see below) Consider connected regions of the map that are colored by either a or c or by b or d. If the a-c region containing A does not contain C, switch colors a and c in that region leaving color a for the center. If region a-c containing A does contain C it follows that the b-d region containing B cannot also contain D as it is surrounded by an a-c region. Then switching colors b and d in the b-d region containing B makes color b available for the center.

Two-color regions as used here all called Kempe chains. Stay tuned.