The 3-Coloring Problem There are 32 possible colorings (legal and illegal)to color a graph with n vertices. The set of all possible colorings can be represented by a complete ternary tree called the search tree. In this tree,each path from the root to a leaf node represents one coloring assignment. ■ An incomplete coloring of a graph is partia/if no two adjacent colored vertices have the same color. Backtracking works by generating the underlying tree one node at a time. If the path from the root to the current node corresponds to a legal coloring,the process is terminated (unless more than one coloring is desired).The 3-Coloring Problem ◼ There are 3n possible colorings (legal and illegal) to color a graph with n vertices. ◼ The set of all possible colorings can be represented by a complete ternary tree called the search tree. In this tree, each path from the root to a leaf node represents one coloring assignment. ◼ An incomplete coloring of a graph is partial if no two adjacent colored vertices have the same color. ◼ Backtracking works by generating the underlying tree one node at a time. ◼ If the path from the root to the current node corresponds to a legal coloring, the process is terminated (unless more than one coloring is desired)