Just make a hole in the center of one side of the polyhedra. Then stretch out the hole, flattening the polyhedra in the process. Eventually you get a planar map, while retaining the same topology as the original polyhedra.
Re:Four-coloring a Dodecahedron
by dietrichepp on Wednesday December 26, 2012 @12:38PM
(#4970037)
Or, in math-speak, the polyhedron is homeomorphic to the sphere, and a stereographic projection of the sphere will preserve the four-color property while projecting the sphere to a plane.
I first thought, "That's exactly what I said," and then I realized that "homeomorphic" isn't exactly a household word.
I could only google a book called "Map Coloring Polyhedra and the Four Color Problem". Unfortunately, it's not available to read online. From what I've found, it seems to me that there is only a handful of proven facts about colorings of some polyhedra.
[ADD]: four color theorem works for every planar graph and it looks like one can make such graph corresponding to any convex polyhedron, so it seems that original OP statement holds.