Изменения

* Для этого для каждой скобки вида <tex> ([\lnot]x_i \lor [\lnot] x_j \lor [\lnot] x_k)_l </tex> добавим вершину <tex> d_l </tex>, соединив её с соответствующими <tex> v_i (\tilde{v_i}), v_j(\tilde{v_j}), v_k(\tilde{v_k}) </tex>, а также со всеми <tex> c_i </tex>, кроме <tex> c_i, c_j, c_k </tex>. Тем самым, <tex> d_l </tex> «не даёт» покрасить все три вершины, отвечающие термам в скобке, в «ложный» цвет (напомним, что все цвета, кроме <tex> c_0 </tex>, мы условились называть «ложными»).<br/>

==== Доказательство корректности сведения ====

# <tex> \Rightarrow </tex>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет <tex>c0</tex>, а вершины, соответствующие ложным термам, &mdash; в соответствующие "ложные" цвета.

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