CASE 4: Assume there is one region with exactly 5 edges.
For this case a consideration of the "duality" shows that at least two of the regions on the 5 boundary edges  have no common border.
Consider each region with a vertex in it and an edge between these vertices when the regions share a boundary.  The resulting graph is planar, so it is not the complete graph on five vertices.

[From Euler's formula, the complete graph on five vertices cannot lie in the plane.] 

Thus at least two of these vertices do not have an edge between them, so there are at least two regions on the 5 boundary edges that do not have a common border.

Sorry, this page requires a Java-compatible web browser. 
1. Remove two of those sides and the related vertices to give a regular map with two fewer regions and four fewer vertices.

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.