(Solved): 4. Bipartite Graphs. A graph is bipartite if all of its vertices can be partitioned into two disjo ...

4. Bipartite Graphs. A graph is bipartite if all of its vertices can be partitioned into two disjoint subsets X and Y so that every edge connects a vertex in X with a vertex in Y. (Alternately, a graph is bipartite if its vertices can be coloured in two colours so that every edge has its vertices colours in different colours; such graphs are also called 2-colourable.) For example each of the three graphs in Figure ?? is bipartite. Design a DFS-based algorithm that returns true if a graph is bipartite and false otherwise. Hint: Think about classifying the vertices as even or odd according to their discovery time. Does such an edge classification give you information you can use?