3. (12 points) K-COLOR. Given a graph G = (V,E), a k-coloring is a function c: V -> {1, 2,..., k} such that cu) #c(v) for every edge (u,v) E E. In other words the number 1, 2, .., k represent the k colors and adjacent vertices must have different colors. The decision problems K-COLOR asks if a graph can be colored with at most k colors. a. The 2-COLOR decision problem is in P. Describe an efficient algorithm to determine if a graph has a 2-coloring. What is the running time of your algorithm? b. The 3-COLOR decision problem is NP-complete by using a reduction from SAT. Use the fact that 3-COLOR is NP-complete to prove that 4-COLOR is NP-complete