4 Graph Coloring II (10 marks) For this question, you are encouraged to use the following fact (you do not need to prove this fact): FACT: Suppose that d is the maximum degree among all vertices in a graph G. Then G has a proper (d + 1)-coloring. (a) Let G be a graph with O(VI) edges. Recall that x(G) is the chromatic number of G. Show that x(G) = O(VIV]). (b) Is this upper bound tight? That is, does there exist a graph with O(IV) edges such that x(G) = 2(VVI)