A bipartite graph is a graphG= (V, E)such that V can be partitioned into two sets (V=V1V2andV1V2=) such that there are no edges between vertices in the same set.

(a) Design and analyze an algorithm that determines whether an undirected graph is bipartite.

(b) Prove the following theorem: An undirected graph, G, is bipartite if and only if it contains no cycles of odd length.

Design and analyze means:

Give pseudocode for your algorithm.

Prove that your algorithm is correct.

Give the running time for your algorithm.