Given an undirected graph G = (V,E), what is the minimum number of colors needed to color the nodes such that no two adjacent nodes have the same color? Please answer the questions below about the following reduction algorithm from the Graph

Coloring Problem to the Class Scheduling Problem.

Algo:

for each vertex in V of the graph G=(V,E) to be colored

create a class

for each vertex v_i in V, i = 1...n,

for each other vertex v_j in V, j = i+1...n,

if (v_i,v_j) is an edge in E of G

add a new student s onto the course roster for both class i and j

feed the class and their course rosters into the class Scheduling Black Box solver

(1) (3 points) If the Class Scheduling Black Box returns a class schedule that uses only k time slots, what does that mean about the colorability of the graph G?

(b) (3 points) If two nodes vi and vj in a graph coloring of G share the same color, what does that mean about class i and j?