Bipartite Graph doubt

Question

Answer 1

Bipartite graph :- Informally,  if there exist two non-empty independent sets such that no edge present within each set elements. 

 

In option A :- if you put K in one ste and j in another set then there is no place to put L anywhere. So we can not put make two independent set here therefore it is not bipartite graph.

Option B  :- correct  

Here two independent sets are  A = { F G D C } 

                                                     B = { E B H I }

so it is bipartite.

Option C :- Wrong, it contains odd length cycle.

Option D :- 

Here two independent sets are  A = { M K P  } 

                                                     B = { L N O }

so it is bipartite.

 

Comments

Option C cannot be a Bi-partite graph since it contains an Odd cycle (LIH).

Also , Option D is Bi-partite since it does not contain any Odd Cycle.

---

Condition for checking whether a graph is bipartite or not:

1. A bipartite graph is 2 colorable means its chromatic number is $2$.
2. A bipartite graph does not contain any odd-length cycle.

Here A and C have odd length cycles. so it is not a Bipartite graph.

B and D have chromatic numbers =2 so it is a bipartite graph.

Answer 2

option B and D are 2 colorable so they are the Bipartite graphs