Question 2: (50 pts) Consider the Vertex Coloring Problem in which we assign different colors to the adjacent vertices on a given graph G=(V,E). The objective is to color the vertices of the graph using minimum number of colors. Input: A graph G=(V,E), where V is the set of vertices and E is the set of edges of the graph G. Output: Color assignments of the vertices using minimum number of colors. Ex: For the graph G in Figure 1, a vertex is a node in the graph and the set of vertices is V={v1,v2,,v10}. An edge is the line between two vertices and the set of edges is E={(v1,v2),(v1,v5),(v1,v6),(v2,v3),(v2,v7),(v7,v10)}. The vertices v1 and v2 are adjacent since there is an edge (v1,v2) between them. On the other hand, v1 and v7 are not adjacent since there is no edge (v1,v7) in the graph. Notice that the adjacent vertices v1 and v2 have different colors (red and green, respectively), whereas non-adjacent vertices v1 and vi can have the same color (red). We observe that we can color the vertices of the graph G in Figure 1 with 3 different colors, i.e., red, green. blue