3
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
