(Solved): 2. The graph coloring problem takes in a graph and asks what isthe fewest number of colors you could ...

2. The graph coloring problem takes in a graph and asks what isthe fewest number of colors you could use to color the graphvertices so that no adjacent vertices are the same color. Forexample, the graph below requires a minimum of 4 colors to producea valid coloring (sample coloring on right):

Graph coloring is useful in scheduling, as well as registerassignment in compilers (vertices are variables, edges connectvariables active at the same time, and colors are registers) andother applications. The greedy coloring algorithm uses colorsnumbered 1 to n. It iterates through vertices of the graph in orderof vertex ID and assigns each vertex the minimum color that is notalready assigned to one of its neighbors. The return value is justthe largest color assigned to a vertex. For example, if the graphabove had vertex IDs numbered from top to bot-tom, the algorithmwould operate as follows and return 4:

Prove that the greedy algorithm is not always correct. Drawgraph and explain difference between greedy and optimal solution.NOTE: don't use the above graph to do this. That was an examplehelping reiterate what greedy coloring is.

We were unable to transcribe this imageWe were unable to transcribe this imageVertex | N(v) colors none 1, 2 1, 2, 3 1, 2, 4 3 1,3 Color assigned 1 (blue) 2 (green) 3 (yellow) 4 (red) 3 (yellow) 1 (blue) 2 (green) Show transcribed image text

Vertex | N(v) colors none 1, 2 1, 2, 3 1, 2, 4 3 1,3 Color assigned 1 (blue) 2 (green) 3 (yellow) 4 (red) 3 (yellow) 1 (blue) 2 (green)