Индукция в графах и теорема Турана

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

Для применения Diamond-леммы необходимо показать, что для пары состояний полученных операциями над вершинами из состояния найдется общее состояние

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

— и смежны, тогда при из при помощи последовательности операций на рисунках (сначала провели операцию над вершиной затем над

Обозначим — вершины смежные и с и с — смежные только с — только с Вес в вершине — в —

Тогда после описанных выше операций получим веса:

• в
• в
• в вес изменится на
• в вес изменится на

Аналогично при помощи последовательных операций над придем к такому же состоянию из Причем количество операций в обоих случаях одинаково, тогда данное состояние потомок в графе состояний, значит, верна Diamond-лемма. Тогда есть единственное конечное состояние с произведёнными операциями, не зависящее от порядка операций и любой путь до него будет длины Получается оба пункта доказаны.