Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 0 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.