The following backtracking algorithm is used to 3-color the graph shown below. Recall that in a proper k-coloring of a graph, nodes are each assigned one of k colors, such that no adjacent nodes have the same color.

Start from source node S.

Color priority is Lavender (L), Orange(O), Teal (T). That is, we will always first try to use L, then O, then T for any given node.

Strategy A: To break ties, always try to assign a color to the lexicographically smallest uncolored node.

Strategy B: To break ties, always try to assign a color to the lexicographically largest uncolored node.

For each Strategy, report the following details:

a. The valid coloring found by the Strategy, for nodes S, A, B, C, D, E in that order. E.g., T, O, L, T, O, L assigns color T to nodes S and C; color O to nodes A and D; and color L to nodes B and E.

b. The total number of nodes (partial solution vectors) in the tree explored by the backtracking algorithm, i.e., the number of times a color is tried out on a vertex during the backtracking.