Take the 2-minute tour ×
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.

Sorry for a silly question, I got confused with the definition of bipartite graph.

What is a necessary and sufficient condition for a bipartite graph.

A bipartite graph has not odd circle

The above property defined as a sufficient conditions, does it mean that all possible even circles is absolutely eligible in bipartite graph?

It's of course a necessary condition, but I am not sure whether it is a sufficient.

Addendum:

What's wrong in the following graph with even circle?

enter image description here

share|improve this question

1 Answer 1

up vote 2 down vote accepted

It is both necessary and sufficient; you’ll find a proof here. And yes, a bipartite graph can have even cycles of any size.

share|improve this answer
    
Thank you very much for the answer, I've edited the question, please take a look at the picture, what's wrong with this even circle, of course it's not a bipartite graph –  fog Dec 26 '12 at 15:40
    
@fog: It is a bipartite graph: you just haven’t split the vertices correctly to show it. The correct vertex sets are $\{A,C\}$ and $\{B,D\}$. –  Brian M. Scott Dec 26 '12 at 15:43
    
thank you very much, now I see you point, I thought splitting comes within definition of the graph as already given, –  fog Dec 26 '12 at 17:08
    
@fog: You’re welcome. If someone says ‘Here’s a bipartite graph’, it will probably come with an appropriate splitting of the vertices, but bipartiteness is actually an inherent property of the graph, not dependent on how it’s presented. –  Brian M. Scott Dec 26 '12 at 17:11

Your Answer

 
discard

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.