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.

  • 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