3COL = {G | $G$ besitzt 3-Färbung}.
Satz: 3COL NPC.
Beweis: 1. 3COL NP (Färbung raten und verifizieren) 2. 3SAT3COL durch folgende Übersetzung ...