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,$dots,$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),$dots,$(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 $v7$ 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.