1. Let G = (V, E) be an undirected (not necessarily connected) graph with each edge colored either blue or red. We are interested in whether the vertices in V can be assigned to two categories: C1 and C2. We take a blue edge (u, v) to mean that u and v should be in the same category, while we take a red edge (u, v) to mean that u and v should be in different categories. G is assignable if there is an assignment of vertices to C1 and C2 such that the meaning of the edges is correct; G is unassignable otherwise.

A. Draw an example of a graph G with six vertices, four blue edges, and four red edges that is assignable. Give an assignment of the vertices to C1 and C2 that demonstrates that G is assignable.

B. Draw an example of a graph G with six vertices, four blue edges, and four red edges that is unassignable. Explain why G is not assignable.

C. Formally state the problem Assignability that answers whether an edgecolored graph is assignable.

D. Using BFS or DFS, design an algorithm Assignable to solve Assignability. Write Assignable in pseudocode. Explain the major changes required to either BFS or DFS to achieve your Assignable algorithm.

E. Analyze the worst-case time complexity of Assignable.