Graph coloring Mapmakers try to use as few colors as possible when coloring countries on a map, as long as no two countries that share a border have the same color. We can model this problem with an undirected graph G = (V, E) in which each vertex repre- sents a country and vertices whose respective countries share a border are adjacent. Then, a k-coloring is a function c : V → {1,2, ...,k} such that c(u) + c(v) for every edge (u, v) € E. In other words, the numbers 1, 2, ..., k represent the k col- ors, and adjacent vertices must have different colors. The graph-coloring problem is to determine the minimum number of colors needed to color a given graph. a. Give an efficient algorithm to determine a 2-coloring of a graph, if one exists.
Please write the code with python, lindo, or matlab
