please answer part b

= Question 5 (20 points) Given a graph G (V, E), a k-coloring is an assignment f : V(G) + {1, ..., k} of a color in {1,..., k} to each of the vertices of v. A coloring f is valid, if for each edge e = (u, v), f(u) + f(v). A coloring is careful, if for each edge e = = (u, v), \f(u) f(x)] > 2. Recall that we have shown in class that the problem of determining whether a given graph G has a valid 3-coloring is NP-complete. a. Prove that for each k > 3, the problem of determining, given a graph G, whether it has a valid k-coloring, is NP-hard. b. Prove that the problem of determining, given a graph G, whether it has a careful 4-coloring, is in P. (Partial credit will be given for solving the same question for careful 3-coloring instead of 4-coloring.) c. Prove that for each k > 5, the problem of determining, given a graph G, whether it has a careful k-coloring, is NP-hard. = Question 5 (20 points) Given a graph G (V, E), a k-coloring is an assignment f : V(G) + {1, ..., k} of a color in {1,..., k} to each of the vertices of v. A coloring f is valid, if for each edge e = (u, v), f(u) + f(v). A coloring is careful, if for each edge e = = (u, v), \f(u) f(x)] > 2. Recall that we have shown in class that the problem of determining whether a given graph G has a valid 3-coloring is NP-complete. a. Prove that for each k > 3, the problem of determining, given a graph G, whether it has a valid k-coloring, is NP-hard. b. Prove that the problem of determining, given a graph G, whether it has a careful 4-coloring, is in P. (Partial credit will be given for solving the same question for careful 3-coloring instead of 4-coloring.) c. Prove that for each k > 5, the problem of determining, given a graph G, whether it has a careful k-coloring, is NP-hard