CASE 3: Assume there is one region with exactly 4 edges.
 

Sorry, this page requires a Java-compatible web browser. 

1. Remove one of those sides and the related vertices to give a regular map with one fewer regions.

2. Color the resulting map with 5 or fewer colors.

3. Since only 4 colors can be on the edges of the removed region, use a fifth color to color the original region.