CASE 2: Assume there is one region with exactly 3 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 3 colors can be on the edges of the removed region, use a fourth color to color the original region.