# Tag Info

Let $G=(V,E)$ be an arbitrary instance of $3$-coloring. Construct a new graph $G'=(V',E')$ as follows: $V'$ contains all the vertices in $V$, and for every edge $e\in E$ it contains a corresponding new vertex $x(e)$. $E'$ contains all the edges in $E$, and for every edge $e=\{u,v\}\in E$ it contains the two new edges $\{x(e),u\}$ and $\{x(e),v\}$. Note the ...