====== Chapter 3.4: Testing Bipartiteness ======
 A bipartite graph is one where the node set //V// can be partitioned into sets //X// and //Y// in such a way that every edge has one end in //X// and the other end in //Y//. Another way to think about it is that the nodes in the set //X// are colored red and the nodes in //Y// are colored blue. A graph is **bipartite** if it is possible to color its nodes red and blue so that every edge has one red end and one blue end.

If a graph //G// is bipartite, then it cannot contain an odd cycle.

===== Testing for bipartiteness =====
First, assume a graph //G// is connected, since otherwise we can just compute its connected components and analyze them separately. Choose a node //s// in //V// and color it red. So all neighbors of //s// must be colored blue, and so on, until the entire graph is colored. Once we are done, we either have a valid coloring of //G// or there is some edge with 2 red or blue ends. In the latter case, //G// is not bipartite.

This procedure is basically BFS, coloring //s// red, layer 1 blue, layer 2 red, and so on. So all odd-numbered layers are blue and even-numbered layers are red. By adding a constant "color" step to the BFS implementation, the overall running time remains O(n+m).

Let //G// be a connected graph and let L_1,L_2,... be the layers produced by BFS starting at node //s//. Then exactly one of the following two things must hold:
  - There is no edge of //G// joining two nodes of the same layer. In this case, //G// is a bipartite graph in which the nodes in even-numbered layers can be colored red and the nodes in the odd-numbered layer can be colored blue.
  - There is an edge of //G// joining two nodes of the same layer. In this case, //G// contains an odd-length cycle and so it cannot be bipartite.


Overall, I'd rate this section a 10. It was very easy to read, especially because it was so similar to our lecture.