Proof: Consider any map on the sphere and a vertex, A, that is not regular.

1. Place a small circular region about the vertex making a new graph with new edges and vertices determined by the intersection of the circle with the original graph.

2. Do step 1 for every vertex on the original map that is not regular. The resulting map is regular.

3. By the assumption, the regular map can be colored with five or fewer colors, so color it.

4.Now remove the circles, coloring the sectors of the original map determined by the added circles by the color of the adjacent region from the regular map.
This colors the original map with the no more than the same number of colors as the regular map.