3-Coloring is a yes/no question, but we can phrase it as an optimization problem as follow...

3-Coloring is a yes/no question, but we can phrase it as an optimization problem as follows.

Suppose we are given a graph G = (V, E), and we want to color each node with one of three colors, even if we aren't necessarily able to give different colors to every pair of adjacent nodes. Rather, we say that an edge (u, v) is satisfied if the colors assigned to u and v are different.

Consider a 3-coloring that maximizes the number of satisfied edges, and let c* denote this number. Give a polynomial-time algorithm that produces a 3-coloring that satisfies at least  edges. If you want, your algorithm can be randomized; in this case, the expected number of edges it satisfies should be at least .