2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Bipartite would require that odd cycles are forbidden... is that synonymous with three-colouring? An example of a graph wold be the graph of a cube $\endgroup$
    – Joffan
    Dec 7, 2016 at 0:34

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .