0
$\begingroup$

Is this question wrong?

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.

Consider a graph of 2 squares stacked on top of each other (7 edges, 6 vertices). It is connected, planar and every face boundary is a cycle of even length (4, 4, 6), but is not bipartite.

$\endgroup$
  • 2
    $\begingroup$ What makes you think that graph is not bipartite? $\endgroup$ – Nick Peterson Jul 18 '14 at 5:41
  • $\begingroup$ Because I couldnt find a partition such that all edges join vertices of one side to vertices of the other side. $\endgroup$ – A_for_ Abacus Jul 18 '14 at 5:50
  • $\begingroup$ Is there a trick to finding it? $\endgroup$ – A_for_ Abacus Jul 18 '14 at 5:51
  • $\begingroup$ possible duplicate of Proving bipartition in a connected planar graph $\endgroup$ – draks ... Jul 18 '14 at 5:52
  • 1
    $\begingroup$ @A_for_Abacus The graph is definitely bipartite. Try thinking about it this way: say that the squares are stacked vertically, and the top left vertex is in $A$. What does this tell you about the middle-left and top-right vertices? What does this tell you about the bottom-left and middle-right? Then the bottom-right? $\endgroup$ – Nick Peterson Jul 18 '14 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.