Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
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

1 Answer 1

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.