Design a Brute Force (Exhaustive Search) algorithm to solve the 3-coloring problem (defined below).

(8 pts) Write the pseudo-code

(2 pts) Analyze the worst-case running time.

3-Coloring Problem: Given 3 colors (Red, Blue, Yellow), and an undirected graph G(V,E) we seek to assign a color to each vertex such that for any edge ( u , v ) E, u and v are assigned different colors. Is the graph G 3-colorable? If yes, then return the color of each vertex. If not, then return a message "The graph cannot be 3-colored".