CODEWITHSUNDEEP
algorithmbipartite
Nathan Chan
Nathan Chan

Reputation: 157

Bipartite Graph or not

enter image description here

I wonder if this graph a bipartite or not. As I found B-C-J is an odd-length cycle however when I draw the BFS no edge join the samen layer. Thanks

Upvotes: 0

Views: 89

Answers (1)

Daniel
Daniel

Reputation: 7724

It's exactly what you said, BCJ makes a cycle so it cannot be a bipartite graph.

There are another cycles, like EGABC.

You cannot have odd-length cycles in bipartite graphs, because it would mean that 2 vertices in the same side would be connected to each other.

Upvotes: 3

Related Questions