====== Section 3.4 Testing Bipartiteness: an Application of BFS ======

A bipartite graph is one that can be separated into two sets such that every edge has one edge in X and the other in Y. This can be represented by a BFS tree by labelling all the odd layers as the layers which contain nodes in the X partition and the even layers contain nodes in the Y partition. Then it is easy to see that there can not be an edge that begins and ends in the same layer, and by the definition of a BFS, there can not be an edge that spans more than one layer difference from the layer in which it has one end. It follows from this then that a bipartite graph can not contain any odd cycles, since an odd cycle must contain an edge that begins and ends in the same layer of the BFS tree. 

This lays down the basis for a very easy addition to be made to the BSF algorithm that will help determine whether a graph is bipartite or not. Simply add an array of size n called Partition and assign all the nodes //n// in an odd layer to be Partition[n] = X and all the nodes in even layers to be Partition[n] = Y. If any edge has both ends being Partition[n] = X or Partition[n] = Y, then the graph is bipartite. Since this all occurs in constant time, it does not bump up the O(n+m) running time of BFS.

This section was fascinating in that it demonstrated that determining bipartiteness of a graph is reliant on the same algorithmic skeleton as the BFS algorithm.