Question

When is a graph said to be bipartite?

(a) If it can be divided into two independent sets A and B such that each edge connects a vertex from to A to B

(b) If the graph is connected and it has odd number of vertices

(c) If the graph is disconnected

(d) If the graph has at least n/2 vertices whose degree is greater than n/2

This question was addressed to me by my college professor while I was bunking the class.

This question is from Bipartite Graphs in chapter Bipartite Graphs of Data Structures & Algorithms II

Answer 1

The correct choice is (a) If it can be divided into two independent sets A and B such that each edge connects a vertex from to A to B

For explanation: A graph is said to be bipartite if it can be divided into two independent sets A and B such that each edge connects a vertex from A to B.