# Proving that a planar graph is bipartite [duplicate]

Let $G$ be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that $G$ is bipartite.

It is quite easy to prove the converse, but how to do this? My line of thought is to assume an odd cycle and show a contradiction, but I don't know where to head? This is homework, so please give hints only, not a full solution.

-

## marked as duplicate by N. S., Jared, Douglas S. Stones, Davide Giraudo, AangJul 17 '13 at 19:19

Hint: Show that all cycles in the graph must be of even length. –  Peter Košinár Jul 17 '13 at 18:18
Another hint: try to use the planarity of the graph, by starting with an embedded cycle and trying to decompose it into "faces". –  user72694 Jul 17 '13 at 18:18
It seems somebody has recently asked the very same question (exact wording, maybe your friend?), see here. –  dtldarek Jul 17 '13 at 18:24

Assume the graph is not bipartite, i.e. there exist odd cycles. Among all those odd cycles pick one with minimal number of faces in its interior. By assumption, this minimal number of faces is at least two, hence there must be a "diagonal" path through the interior of our odd cycle. With this diagonal we obtain two smaller (again, with respect to number of faces contained) cycles, hence by assumption both are even. But that leads to a contradiction: The total length of the two smaller cycles differs from the length of the original one by twice the diagonal length.

-