GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 25

Question

Which of the following graph is NOT bipartite? (Mark all the appropriate choices)

• A.
  
• B.
  
• C.
  
• D.
  

Answer 1

Bipartite graphs are equivalent to two-colorable graphs. All acyclic graphs are bipartite. A cyclic graph is bipartite iff all its cycles are of even length.

The second option is not bipartite because it has a triangle (odd length cycle) subgraph (shown in magenta color below).

All other graphs are having cycles of even length and hence are bipartite.

So, the correct answer is $(B).$

Comments

@yogesh then 8 should be connected with 2 but it’s not.

---

there no need  , its not a complete bipartite graph.

---

We know that every bipartite graph is 2-colorable. So if a graph is not 2-colorable then the graph is not bipartite.

Try coloring the graph and you will find that Option B is 3 colorable. hence it is not bipartite, rest are bipartite.