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

Пример графа показан на рисунке. Множество содержит вершину, множество — вершину.

_________________________________________________________________________________________________________________________________________________________________________________

Оценка. Для графа и некоторого множества его ребер через обозначим граф, получающийся из графа удалением всех его ребер, входящих в , т.е. граф .

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство. Пусть в графе ровно компонент связности. Если добавить к все ребра из множества , то получится компонент связности. Поэтому если мы будем последовательно добавлять в граф те ребра из , которые уменьшают число компонент связности, то, добавив в точности ребер из , получим компонент связности (поскольку добавление каждого ребра уменьшает число компонент связности не более, чем на 1). Добавление остальных ребер из уже не уменьшит количество компонент связности. Аналогично к графу можно добавить такие ребер из множества , что в итоге получаются все компонент связности графа . Но если к графу добавить и те, и другие ребра (в общей сложности ребер), то граф станет связным. Следовательно, и, значит, .

_________________________________________________________________________________________________________________________________________________________________________________

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

следовательно, .