Изменения
Нет описания правки
Покажем теперь, что такой граф будет (n+1)-раскрашиваемым тогда и только тогда, когда исходная формула принадлежала 3CNFSAT.
# <math> \Rightarrow </math>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет c0, а вершины, соответствующие ложным термам, - в соответствующие "ложные" цвета.
# <math> \Leftarrow </math>. Построим по раскраске графа набор переменных <math> \{x_i\}_{i=1}^n </math>, в котором <math> x_i </math> истинно тогда и только тогда, когда <math> v_i </math> покрашена в цвет <math> c_0</math>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истину, так как по постронию в каждой скобке есть хотя бы один истинный терм.
