Graph Coloring: Consider a graph with 5 modes corresponding to variables numbered 1, 2, 3, 4, 5 and edges between the following nodes: 1-2, 2-3, 3-4, 4-5, 1-5, 1-4, 2-4, 3-5. Each variable can take three values: A, B, or C. Two variables corresponding to node which are connected by an edge must have different values.

a. What is the domain for each variable?

b. Draw the constraint graph.

c. Solve this problem by hand by using the minimum remaining value heuristic to choose the next node to expand in the search tree. Break ties using the degree heuristic. Use the least-constraining-value heuristic to pick a value. Any remaining ties can be broken arbitrarily. At each step explain your reasoning.

d. Assume that node 1 has value C and node 5 has value B. Apply forward checking to reduce the domains of (some) of the other variables. Explain your answer.

e. Use arc-consistency (repeatedly) to further reduce the domains of the remaining variables. Explain your answer.