这是 2023 年春北雷村男子职业技术学院 sipser 课程中的一道作业题
题目中给出了一种根据 3CNF 构造图的方式，要求我们证明 3COLOR 问题是 NP-complete 的。
3COLOR 指的是，给定一张图 G，用 3 种颜色给图中的点着色，以使得没有两个相邻的节点颜色相同。可以用上述着色方式着色的图构成的集合为 3COLOR。
而 3SAT 问题指，给定命题
其中 \(c_i\) 为 3 个变量的析取构成的子句，变量可以是正的布尔变量或负的（\(x_i\) 或 \(\neg x_i\))。上述命题公式被称为 3-cnf。3SAT 是可满足的 3-cnf 的集合。
题面中给出的构造方式：
令 \(\phi = c_1 \wedge c_2 \wedge \cdots \wedge c_l\) 为建立在变量 \(x_1,x_2,\cdots,x_m\) 上的 3-cnf，建立含有 \(2m+6l+3\) 个点的图 \(G_\phi\)。为每个变量分配 2 个点，每个子句再分配 6 个点，另外再加上 3 个额外节点。
定义了术语 “gadgets” 来描述图（gadget 是满足某种条件的子图）。
\(G_{\phi}\) 中每个变量对应的两个点构成 variable gadget，每个子句都有两个 OR-gadgets（形状见上图），此外还有一个 palette gadget。 两个 OR-gadgets 的底部两个点（共四个）会和图中的其它点合并。
将 palette gadget 中的点分别标记为 T，F，R，将 variable gadget 的两个点分别标记为 \(+\) 和 \(-\)， 并连接到 palette gadget 的 R 节点。
在每个子句中，将其中一个 OR-gadget 最顶上的点连到 palette 的 F 点，并将该 OR-gadget 的底下两个点与另一个 OR-gadget 的顶部点合并。这一步的图画出来长这样：
这样当前子句的两个 OR-gadgets 会剩下 3 个底部节点没有合并，它们会按照如下规则与 variable gadgets 中的点合并：如果当前子句包含变量 \(x_i\)，就将一个底部节点与变量 \(x_i\) 的 variable gadget 中的 \(+\) 节点合并，如果包含 \(\neg x_i\)，就和对应的 \(-\) 节点合并。子句中包含 3 个变量，正好使得这 3 个节点与其它点合并。
按照上述方式，每个 3-cnf 公式 \(\phi\) 可以导出一个图 \(G_\phi\) 。其中变量若为真，则分配颜色 1，若为假，则分配颜色 2。图中点 R 对应颜色 3. 并且令 palette gadget 的 F 点颜色为 2， T 点颜色为 1.
OR-gadget 的最底下两个点对应变量的输入，若它们均为假，会使得 OR-gadget 顶部点的颜色也为 2. 但这与 F 的颜色为 2 冲突。
因此 ，按上述方法能够将 3-SAT 规约到 3-COLOR 问题。根据 COOK-LEVIN 定理，3-COLOR 是 NPC 问题。