Гуляем по графу

Пусть существуют два хороших хороших множества которые содержат различное количество элементов. Без ограничений общности считаем, что

Покажем, что не является максимальным по включению.

Действительно, пусть и — множество непересекающихся путей из и соответственно в Если существует путь который не пересекается с любым путем из то мы можем добавить его начало в следовательно, не является максимальным по включению. Далее считаем, что все пути из пересекаются какими-либо путями из

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

Пусть — число всех ребер в путях из на шаге данного алгоритма, — число общих ребер в путях из и на шаге данного алгоритма. Рассмотрим величину

на шаге данного алгоритма. Поскольку количество общих ребер увеличивается на число большее, чем количество ребер в перестраиваемом пути

Таким образом, мы можем совершать шаг алгоритма каждый раз, пока существует путь из который пересекается с каким-то путем из и не имеет общий конец с любым путем в но по определению, то есть рано или поздно все пути из таковы, что удовлетворяют ровно одному из условий

1.

имеют общий конец с каким-то путем из

2.

не имеют общих вершин с любым путем из

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