3
$\begingroup$

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

1 Answers 1

3

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

  • 0
    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 graph2012-12-26
  • 0
    @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\}$.2012-12-26
  • 0
    thank you very much, now I see you point, I thought splitting comes within definition of the graph as already given,2012-12-26
  • 1
    @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.2012-12-26