How do you check if a graph is bipartite?
Try to -color it. If you succeed, it is bipartite. If you hit a contradiction (two adjacent nodes with the same color), it is not. The algorithm is simple: pick a node, assign it color . All its neighbors get color . All their neighbors get color . Continue until done. If you ever need to color a node but its neighbor already has the same color, you have found an odd cycle. The graph fails the test. If you finish without conflicts, the graph is bipartite.