51
правка
Изменения
→Пример
Заметим, что если в графе <tex>G</tex> был независимый подграф с <tex>k</tex> вершинами, то в <tex>H</tex> между всеми вершинами подграфа будут ребра, следовательно, в графе <tex>H</tex> будет клика с <tex>k</tex> вершинами.
С другой стороны, если в <tex>H</tex> есть клика с <tex>k</tex> вершинами, значит между всеми вершинами клики проведены ребра, а значит их не было в графе <tex>G</tex>. Т.о. Таким образом, в графе <tex>G</tex> был независимый подграф с <tex>k</tex> вершинами.
Из всего сказанного следует, что <tex>IND \le CLIQUE</tex>.
