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.
Justification:
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.
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.