Describe an efficient algorithm for checking bipartiteness based on the above approach. What is the running time of your algorithm and why?

Problem Description Given a graph, the goal is to check whether the graph is bipartite or not. A graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint subsets (S, T) such that every edge (u, v) ∈ E has one endpoint in S and the other endpoint in T, i.e., either u belongs to S and v belongs to T or vice versa.

There are other equivalent definitions of a bipartite graph. A graph is bipartite if and only if it has no odd length cycle, i.e., no cycle in the graph has an odd number of edges. Note that if a graph has no cycles it is bipartite (hence trees are bipartite graphs). It is an interesting exercise for you to show that the above two definitions are equivalent (highly recommended if you want to get a taste of graph theory). But that is not the goal of this exercise. Using the odd cycle definition one can use DFS or BFS to elegantly check whether a graph is bipartite in linear time, i.e., O(m + n) time. 

The goal of this exercise is to explore yet another approach to check bipartiteness and is based on the following idea. You must argue that the idea is correct (as mentioned below) and implement the idea as an algorithm that checks for bipartiteness of a graph. Let G = (V, E) be the input graph that you want to check for bipartiteness. We first transform G into a new graph G’ = (V’ , E’ ) as follows. For each each node v ∈ V , construct two nodes v1, v2 ∈ V’ and for each edge (u, v) ∈ E, create two edges (u1, v2) and (u2, v1) in E’ . This completes the description of constructing G’ from G. See Figure 1 for an illustration.

The idea of this construction is that it reduces the problem of checking bipartiteness of G to checking the number of connected components of G’ as stated in the following theorem.

Theorem 1. Let C be the number of connected components in G. Then the number of connected components in G’ is 2C if and only if the graph G is bipartite. Your first goal is to give a proof of the above theorem (see the submissions instructions below).

To get an idea of why the above theorem might be true, see the two examples given in Figures 1 and 2. The graph in Example 1 is bipartite (no cycle) and the number of connected components is 1; it is 2 in G’. The graph in Example 2 is not bipartite (odd cycle of length 3) and the number of connected components is 1; it is 1 also in G’ . Your second goal is to use the theorem above to give an efficient algorithm for checking bipartiteness.

Examples provided in attachment.

(a) Proof of Theorem 1. (30 points)

(b) Describe an efficient algorithm for checking bipartiteness based on the above approach. What is the running time of your algorithm and why? (20 points)

(c) Code up your solution in C++. Your code should be well commented. Your code should compile, otherwise no points. (50 points)