3-Färbbarkeit

3COL = {G | $G$ besitzt 3-Färbung}.

Satz: 3COL $\in$ NPC.

Beweis: 1. 3COL $\in$ NP (Färbung raten und verifizieren) 2. 3SAT$\le_{P}^{}$3COL durch folgende Übersetzung ...