The graph k-coloring problem is defined as follows: Given a graph G and an integer k, is G k-colorable?, i.e. can we assign one of k colors to each node of G such that no edge has both of its ends colored by the same color. The graph 3-coloring problem is NP-complete and this fact can be proved by a reduction from 3SAT. As a part of the reduction proof, we assume that there are three colors GREEN, RED and BLUE. For variable a, let a! denote NOT(a). We associate with each variable a, a "gadget" consisting of 3 nodes labeled a, a' and X. This gadget is shown at the right in the diagram above. X is common for all variables and is labeled blue. If a is TRUE (respectively FALSE) in a particular assignment, node a is colored green (respectively red) and node a' is colored red (respectively green). With each clause we associate a copy of the gadget at the left in the diagram above, defined by the graph H = (VE) where V = {p, q, r, s, t, u} and E = {(p, q), (q, r), (rp), (s, t), (t, u), (up), (qp)}. Nodes t, u and r from this copy of the gadget are connected to the nodes constituting the literals for the clause, in left to right order. Consider a clause in the 3-CNF expression: a + b' + c. We must color the above gadget using the colors red, blue and green in such a way that no two adjacent nodes get the same color. In each choice below, you are given an assignment for the variables a, b, and c and a possible assignment of colors to some nodes in the gadget above. Indicate the choice of colors that is valid for the given truth assignment: a) (a=TRUE, b=TRUE, c=TRUE, t=red, u=blue, p=red) b) (a=FALSE, b=TRUE, c=FALSE, t=blue, u=green, p=green) c) (a=TRUE, b=FALSE, c=TRUE, t=blue, r=red, p=green) d) (a=TRUE, b=FALSE, c=TRUE, t=red, u=blue, p=red)