Exercise 11.10. An undirected graph G = (V, E) is called bipartite if it contains no odd cycle, i.e., no cycle has an odd number of edges. Note that a graph with no cycles is also bipartite. We are going to show an important property of bipartite graphs: its vertex set can be partitioned into two disjoint sets A and B, i.e., A B = V and A B = , such that all the edges are between vertices in A and vertices in B in other words, there are no edges between any two vertices in A and any two vertices in B. The goal of this problem is that, given a connected bipartite graph G = (V, E), to find a partition of the vertex set into A and B such that all edges are between some vertex in A and some vertex in B. (a) Do Breadth-First Search (BFS) on G from some starting vertex, say a, and compute the distance (i.e., the level in the BFS tree) of every vertex v to a. Show that if G is bipartite then there are no edges between vertices in the same level. (Hint: Use the odd cycle property of bipartite graph). (b) Show that you can output the sets A and B in linear time, i.e., O(|V | + |E|) time.