Problem: Bipartiteness

Let G(V,E) be an undirected graph given in adjacency list representation.

Problem 3: Bipartiteness (20 points) Let G(V, E) be an undirected graph given in adjacency list representation. Say thet G is bipartite if and only if the vertives of V can be bipartitioned to sets Vi and VR (ie VL VR = V and VrnVr =such that all edges e E have exactly one endpoint in ll and exactly one endpoint in VR. Give an 0(V + E) algorithm that Either proves that G is bipartite by bipartitioning V to V and VR si that al edges have exactly one endpoint in Vi and exactly one endpoint in VR Or proves that G is not bipartite by returning an odd length cycle formed by edges in E Problem 3: Bipartiteness (20 points) Let G(V, E) be an undirected graph given in adjacency list representation. Say thet G is bipartite if and only if the vertives of V can be bipartitioned to sets Vi and VR (ie VL VR = V and VrnVr =such that all edges e E have exactly one endpoint in ll and exactly one endpoint in VR. Give an 0(V + E) algorithm that Either proves that G is bipartite by bipartitioning V to V and VR si that al edges have exactly one endpoint in Vi and exactly one endpoint in VR Or proves that G is not bipartite by returning an odd length cycle formed by edges in E