$*!$ Exercise $10\mathrm{.}4\mathrm{.}2$: The coloring problem is: given a graph $G$ and an integer $k,$

is $G"k-$color able"; that is$,$ can we assign one of $k$ colors to each node of $G$ in

such a way that no edge has both of its ends colored with the same color. For

example, the graph of Fig. $10\mathrm{.}1$ is $3-$colorable, since we can assign nodes $1$ and

$4$ the color red, $2$ green, and $3$ blue. In general, if a graph has a $k-$clique, then

it can be no less than $k-$colorable, although it might require many more than $k$

color s$.$

Figure $10\mathrm{.}13$: Part of the construction showing the coloring problem to be NP$-$

complete