Связность и связные подграфы (клики)

(a) 

Оценка. Занесём 2 в числитель и оценим каждое слагаемое следующим образом

Получим

Так как у каждой вершины степень у каждой вершины в графе равны то каждая в числителе встретиться ровно раз, следовательно

Пример. Поставим во все вершины получим

(b) Будем доказывать от противного.

Если граф нельзя покрасить в цветов, то в графе есть вершина степени меньше чем то удалим с рёбрами. Полученный граф также нельзя будет покрасить в цветов, иначе покрасим его, а потом докрасим удалённую вершину. Продолжим этот процесс, он конечный, так как в графе конечное число вершин.

Значит, найдётся подграф, в котором степени вершин хотя бы Поставим в вершины этого подграфа а во все остальные вершины графа Тогда значение выражения станет равным а это противоречит тому, что — максимум выражения

(c) Кликой графа называется подмножество его вершин, любые две из которых соединены ребром. Аналогично определяется антиклика

Пример. Найдём в графе максимальную клику, в его вершины поставим а в остальные

Оценка.

Рассмотрим расстановку, на которой достигается Если там есть вершина с 0, удалим её. По предположение

если максимальная антиклика не уменьшилась, и

если максимальная антиклика уменьшилась. Таким образом сделаем все числа ненулевыми.

Обозначим — сумму чисел в смежных с вершинах. Заметим, что если и — несмежные вершины и то можно заметить на Общая сумма не измениться, а увеличиться, противоречие. Следовательно, если и — несмежные вершины, то

Рассмотрим антиграф, проверим два случая:

1) Если он связен. Значит, для любых вершин и обозначим это число за Следовательно по предположению

Рассмотрим вершину максимальной антиклики.

Следовательно, число в плюс в вершинах, не смешных с меньше Просуммируем по врем вершинам максимальной антиклики. Мы посчитали каждое число неменее 1 раза, значит сумма всех меньше, чем . Противоречие, следовательно, такое невозможно.

2) Антиграф не связен.