CASE 4: Assume there is one region with exactly
For this case a consideration of the "duality" shows that
at least two of the regions on the 5 boundary edges have no common
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
[From Euler's formula, the complete graph on five vertices cannot lie in
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.