NP-полнота задачи о раскраске графа

Формулировка задачи

Даны граф [math] G = \lt V, E\gt [/math] и число [math] k [/math]. Нужно проверить, правда ли, что можно раскрасить вершины графа в [math] k [/math] цветов так, чтобы любые две вершины, соединённые ребром, имели разные цвета.

Утверждение

Сформулированная выше задача NP-полна.

Доказательство

1. Сперва покажем принадлежность задачи классу NP.
   

Сертификатом для решения данной задачи будет последовательность [math] \{c_i\}_ {i=1}^{n}[/math], где [math] n = |V| [/math], а [math] c_i [/math] обозначает цвет i-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке [math] [1, k] [/math].