证明3-可着色问题是NP完全问题

要证明一个问题是NP完全问题，需要证明两个部分：
1. 该问题属于NP问题集合；
2. 该问题可以用NP完全问题进行多项式时间归约。

首先，我们证明3-可着色问题属于NP问题集合。假设我们有一个图和一组着色，我们可以在多项式时间内验证该着色是否正确。因为我们只需要检查每个顶点是否与其相邻的所有顶点的颜色不同。因此，3-可着色问题属于NP问题集合。

接着，我们需要证明3-可着色问题可以用NP完全问题进行多项式时间归约。我们选择SAT问题作为NP完全问题，并将其转化为3-可着色问题。具体的，我们将每个布尔变量转化为图中的一个顶点，将每个子句转化为一个大小为3的子图。如果子句中有变量的否定，则我们将该变量对应的顶点的颜色标记为1，否则标记为2。通过这种方式，我们可以将SAT问题转化为一个3-可着色问题。

因此，我们证明了3-可着色问题是NP完全问题。