Question#$4$: $(6$ pts$)$ Suppose that to color a graph properly we choose a starting vertex and a first color to color as many vertices as possible. Then we select a new vertex and a new color and color as many vertices as possible. We repeat this process until all the vertices of the graph are colored or all the colors are exhausted.

a$)$ Use the algorithm to color the following graph:

V$1$

V$2$

V$3$

V$4$

V$5$

V$6$

b$)$ Calculate the time complexity of the greedy method and compare it to the backtracking algorithm.

c$)$ Suppose we are interested in minimizing the number of colors used in coloring used to color the graph. Does the greedy approach guarantee an optimal solution? Justify your answer.