If every node has degree three and the faces are three-colorable, then the graph bipartite.

Question

Consider a planar map in which every node has degree three. Suppose that the faces can be three-colored. Prove that the graph of the map is bipartite.

I've tried to draw it out but it seems impossible to me.

Answer 1

Suppose for the sake of contradiction that your planar graph is not bipartite. Then there exists some face $F$ that is bounded by an odd number of edges. Since each vertex of the graph has degree three, for each edge on the boundary of $F$ there exists a single face bordering $F$ such that if two edges on the boundary are incident to the same vertex, then their corresponding faces border each other.

So once you color $F$, there is a "ring" of faces around $F$ that must be colored differently from $F$, and colored in an alternating fashion to induce a proper coloring. But since there are an odd number of faces in this "ring," you see that you will need more than two additional colors. So the graph cannot be three-colorable.

Answer 2

At each vertex, the colors red, green, and blue appear around it in either counterclockwise or clockwise order. This defines a bipartition.