# 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

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.