planar Graph problem

In a planar representation of G , every regions (for example $R_1$) surrounded with even EDGES.

Prove that : G is bipartite.

(I think can use "G has no odd cycles then G is bipartite.")

-
what does "every region(R) covered with even degrees" mean? – Chris Eagle Oct 29 '12 at 18:35
@World Does it mean that every face has even degree? – EuYu Oct 29 '12 at 18:45
@ChrisEagle for each region R1,R2,... then number of edges sides a region be even. – World Oct 29 '12 at 19:17

1 Answer

Perhaps someone can fix this up a bit, it feels like there should be a more elementary argument, but I couldn't find a nice way to rigorously prove this statement without appealing to a cycle basis.

In a planar graph, the set of interior faces provides a cycle basis for the cycle space of $G$. It follows that every simple cycle in the graph is represented as a symmetric difference of the cycles surrounding the faces of the vertices. Since every cycle is the cycle basis is of even length, it follows that every cycle in their span is also of even length (this is rather easy to see from the definition of symmetric difference). It follows that the graph is bipartite.

-
i don not realized symmetric difference. can you improve and more your explanation? – World Oct 29 '12 at 20:34
The symmetric difference is a set theoretic operation. Basically it allows us to join simple cycles in such a way that the union is still a simple cycle. You might always want to take a look at the cycle space. – EuYu Oct 29 '12 at 21:41