Consider the following two problems: Problem A: Given a graph G=(V,E) with vertex set V={1,2,,n}, the problem is to decide if the vertices of G can be colored using two colors (say red and blue) such that for any edge e={x,y}E, the endpoints x,y do not have the same color. Problem B: Given a set of variables U={x1,x2,,xm} and a set of clauses C={c1,c2,,cm} where each clause is the OR (denoted by the symbol ) of exactly two literals (eg. a clause will look like x1x5 ). The problem is to decide if C is satisfiable. That is, decide if there is an assignment of true/false values to the variables in U so that each clause is C evaluates to true under the assignment. For a instance of Problem A given by a graph G=(V,E) with V={1,2,3,,n}, we construct an instance (U,C) of problem B as follows: - U={x1,x2,,xn} (one variable per vertex in V ), - For each edge {i,j}E, we introduce two clauses xixj and xixj into C. Answer the following questions: 1. For the graph G given in Figure 1, give the instance of Problem B that is constructed. 2. Show that G=(V,E) is a yes-instance of problem A if and only if the constructed instance (U,C) is a yes-instance of problem B. Figure 1: Graph for Question 1