How to reduce 2-coloring to 2-SAT Let $G=(V,E)$ be an undirected graph in which $V = \{v_1,v_2,\dots,v_n\}$.

I need to describe a reduction from the 2-coloring problem to the 2-SAT problem (in polynomial time).

I thought of splitting each vertex $v_i$ into $v_i^*$ and $v_i^{**}$, one for each color. Then I was thinking about making for each edge $(u,v)\in E$, two correspond literals: $(u^* \lor v^*)$ and $(u^{**} \lor v^{**})$.

I know I'm on the right track but I can't prove it.

any ideas?
If all you require is a polynomial-time reduction, then test in polynomial time if $G$&nbsp;is $2$-colourable. If it is, map it to the formula&nbsp;$X$; if it isn't, map it to $X\land\lnot X$.