平面图三着色

平面图的三着色问题也是 NPC 问题，这也可以通过一般图三着色问题归约到该问题证明。