Комбинаторика на Питергоре

Рассмотрим граф знакомств математиков. По условию этот граф хордовый, т.е. в нем любой цикл из или более вершин содержит хорду (пару смежных вершин, не соседних в цикле). Докажем, что для хордового графа выражение где — количество клик (полных подграфов) в на вершинах, равно числу компонент связности графа

Предположим, что это не так, и рассмотрим в качестве наименьший по числу вершин контрпример. Ясно, что граф содержит больше одной вершины и связен (иначе одна из компонент связности была бы меньшим контрпримером). Удалим из графа произвольную вершину пусть новый граф распался на компоненты Пусть , — подграфы в соответственно на соседях вершины Несложно видеть, что

где слагаемое соответствует клике слагаемые — кликам, не содержащим слагаемые — — кликам, содержащим (при удалении из них вершины меняется четность, а стало быть, знак в выражении для ). В силу минимальности контрпримера Проверим, что при всех Предположим противное, тогда вершины одного из графов можно разбить на два непустых подмножества так, что ни одно ребро не ведет из в Рассмотрим наименьший по числу ребер путь из в в графе Тогда цикл не имеет хорды в графе

Мы проверили, что при всех Тогда по формуле т. е. граф оказался неконтрпримером.