Załóżmy, że znaleźliśmy wartościowanie które spełnia formułę. Możemy wtedy wybrać z każdej formuły po jednym literale, który jest prawdziwy w takim wartościowaniu. Ten zbiór jest niezależny ponieważ zawiera tylko po jednym literale z każdej klauzuli (nie ma krawędzi typu 2), i wartościowanie nie dopuszcza żeby literał i jego negacja były jednocześnie prawdziwe (nie ma krawędzi typu 1).
Z drugiej strony, załóżmy, że znaleźliśmy zbiór niezależny rozmiaru k. Nie może on zawierać dwóch literałów w jednej klauzuli, ponieważ byłyby one połączone krawędzią. Zatem musi zawierać po jednym literale w każdej z k klauzul. Nie może zawierać też żadnego literału jednocześnie z jego negacją, ponieważ byłyby one też połączone krawędzią. Oznacza to że jeśli wybierzemy wartościowanie które nada tym k literałom wartość prawda, to będzie ono spełniało początkową formułę.
Z Kategoria:Teoria obliczeń
ja:最大独立集合問題