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.