Let G $=($V$,$E$)$ be an undirected graph with vertex set V and edge set E$.$ A $3-$coloring of G is a map $\backslash$chi : V $->\{$R$,$ B$,$ Y $\}$ such that if $\{$x$,$ y$\}$ in E then $\backslash$chi $($x$)=\backslash$chi $($y$).($Here R$,$ B$,$ Y represent the colors red, blue, yellow.$)$

$17$

$($a$)$ Suppose n $>1$ and let Vn $=\{0,1,...,$n$1\}$ and let Gn $=($Vn$,$En$)$ be an undirected graph with vertex set Vn$.$ For each i$,0<=$ i $<$ n let Ri$,$ Bi$,$ Yi be propositional variables. $($Intuitively Ri assert that node i is colored red, and Bi$,$Yi assert it is colored blue, yellow, respectively.

Give a propositional formula An using the variables $\{$Ri$,$ Bi$,$ Yi $|0<=$ i $<$ n$\}$ such that An is satisfiable iff Gn has a $3-$coloring. Do this in such a way that An can be computed efficiently from Gn $($e$.$g$.$ don$$t define An to be R$1$ if Gn has a $3-$coloring and $($R$1$R$1)$ otherwise$).$