$5.[2$ marks$]$ A graph G has a valid $8-$coloring if the vertices in G can be assigned one of $8$ colors such that no two adjacent vertices are assigned the same color. Consider:

COLOR $=\{$G$|$ G is a simple graph that can be $8-$colored. $\}.$

Show that COLOR is in NP$.$

$6.[3$ marks$]$ Consider the following language:

EC $=\{$G$|$ G is a connected undirected graph that has an Euler cycle$\}.$

$($a$)$ Prove that EC is in P$.$

$($b$)$ Explain why some people believe that EC is NP$-$complete.

$($c$)$ What are the immediate societal implications of a formal proof that EC is NP$-$complete?

$7.[5$ marks$]$ Prove that FUN$-$SAT is NP$-$complete:

FUN$-$SAT $=\{$$|$ is a boolean formula that has at least $3$ satisfying assignments$\}.$

Verify the correctness of your reduction.