Call an undirected graph k-colorable if one can assign each vertex a color drawn from {1, 2, . . . , k} such that no two adjacent vertices have the same color. We know that bipartite graphs are 2- colorable. (a) Prove that if the degree of every vertex of G is at most , then the graph is (+ 1)-colorable. Show how to contruct, for every integer > 0, a graph with maximum degree that requires + 1 colors. (b) Prove that if G has n vertices and O(n) edges, then it can be colored with O(n) colors.