Complexite et np completude

bonjour a vous tous. Mon problème est le suivant je veux montrer que le problème 3 color est un problème np complet. le problème 3 color consiste a colorier tous les sommets d un graphe avec 3 couleurs de telle sorte que deux sommets adjacents n'aient jamais la même couleur.
je peux deja montrer que 3 color est np en utilisant le vérifieur suivant:
1- vérifier que chaque sommet du graphe g est colorie.
2- vérifier que le nombre de couleurs utilisées pour colorier le graphe vaut 3.
3- pour toute arête (a,b) vérifier que le sommet a a une couleur différente de celle du sommet b.
le vérifieur me coute donc en complexité o(n+m) avec n étant le nombre de sommets et m le nombre d'arêtes. je peux donc conclure que 3 color est dans NP.
La où je coince c'est sur la reduction de 3Sat a 3Color. Merci pour votre aide.