# Face Boundary and bipartite question classification

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.

• What makes you think that graph is not bipartite? – Nick Peterson Jul 18 '14 at 5:41
• Because I couldnt find a partition such that all edges join vertices of one side to vertices of the other side. – A_for_ Abacus Jul 18 '14 at 5:50
• Is there a trick to finding it? – A_for_ Abacus Jul 18 '14 at 5:51
• possible duplicate of Proving bipartition in a connected planar graph – draks ... Jul 18 '14 at 5:52
• @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? – Nick Peterson Jul 18 '14 at 5:52