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.")
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.")
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.