In class we discussed an algorithm to color the vertices of an n vertex graph with 2 colors so that every edge gets exactly 2 colors (assuming such a coloring exists). We know of no such algorithm for finding 3-colorings in polynomial time. Here we'll figure out how to color a 3-colorable graph with O(n) colors. (a) Give a greedy polynomial time algorithm that can properly color the vertices with A+1 colors, as long as every vertex of the graph has degree at most A. (b) Give a polynomial time algorithm that can properly color the graph with O(vn) colors, as long as the input graph is promised to be 3-colorable. HINT: If a vertex v has more than n neighbors, then argue that the subgraph of the neighbors of v must be bipartite, and use the algorithm from class to color v and its neighbors with 3 new colors. Continue this process until every vertex has less than n neighbors, and then use the algorithm from part (a)