The graph coloring problem: An undirected graph coloring problem consists of assigning colors to all the nodes of the gr

[answerhappygod]

The graph coloring problem: An undirected graph coloringproblemconsists of assigning colors to all the nodes of the graph so thatthere are no two adjacent vertices (neighbors)that have the same color and at most k colors are used to color thegraph. Formally,given a graph G = (V,E) and a number k, the task is to decide ifthe graph can be colored using asmaximum k colors such that no two adjacent vertices have the samecolor.Prove that 2-COLORATION is in P.