3-Colorability

Problem Definition

Given an undirected graph $G=(V,E)$, can the nodes be colored in three colors so that no adjacent nodes have the same color?

Prove 3-Colorability is NP-complete

1. Prove its NP
2. Choose 3-SAT Problem
3. Prove that 3-SAT Problem ${\le }_P$ 3-Colorability Given any 3-SAT instance $\Psi$, construct an instance $G$ of 3-Color that is 3-colorable if and only if $\Psi$ is satisfiable.