On montre les liens entre les problèmes de graphes et le calcul propositionnel. Dans un sens, on part de 2-SAT et on utilise un algorithme sur les graphes pour montrer que le problème est dans P (et même qu'il est NL-complet). Dans l'autre sens, on part de CLIQUE dont on montre la NP-complétude à l'aide de SAT.