Consider the k-color problem, which is to assign one out of k colors to each node of a graph so that for every arc (i, j), nodes i and j have different colors.
(a) Suppose we want to choose the colors of countries in a world map so that no two adjacent countries have the same color. Show that if the number of available colors is k, the problem can be formulated as a k-color problem.
(b) Show that the k-color problem has a solution if and only if the number of nodes can be partitioned in k or less disjoint subsets such that there is no arc connecting a pair of nodes from the same subset.
(c) Show that when the graph is a tree, the 2-color problem has a solution.
(d) Show that if each node has at most k - 1 neighbors, the k-color problem has a solution.