BIpartite graph: One where th enode set V can be partitioned into sets X and Y in a such a way that every edge has one end in X and the other in Y(Every edge joins one red node to a blue node). Examples of non-bipartite graphs are: A triangle (3 nodes), generally if a graph G has an odd cycle, then it cannot be partite. If a graph G is bipartite, then it cannot contain an odd cycle. How to determine if a graph , G is bipartite??? We should be able to determine for ourselves whether there exists a partition into red and blue nodes. How difficult is this?? Designing such an Algorithm Odd cycles are the only obstacle to getting a bipartite graph. Step 1: Assume the graph is connected. Then, pick any node and color it red, and color all its adjacent nodes blue. Then color red the neighbors of these adjacent nodes and so on. This resembles how BFS is carried out because we also move out to a node's neighbors, color, and move to their respective neighbors i.e Coloring odd-numbered layers blue and even-numbered layers red. We can simply take the implementation of BFS and add an extra array Color over the node. We add color red to a node being added to a list, L[i+1] if i+1 is even, and blue otherwise. This will also take O(m+n) time. A connected graph, G can either be bipartite(there are only edges between nodes of different layers) or not bipartite(if there is a node between two nodes of the same layer). Proof is on Page 96.

I pretty much understood what we mean by bipartite and how it is an application of the BFS algorithm, thus I give it a scale of 9/10.