Изменения

Пусть <tex>\mathbb{G'}</tex> {{---}} граф, полученный из <tex>\mathbb{G}=<\mathbb{V},\mathbb{E}></tex> добавлением ребер, при этом в <tex>\mathbb{G'}</tex> нет полного паросочетания, но оно появляется при добавлении любого нового ребра.

Так как новых вершин не добавлялось, то <tex>\mathbb{G'}=<\mathbb{V},\mathbb{E'}></tex> Пусть <tex> U = \{ v \in \mathbb{V}: deg_{G'} (v) = n - 1 \}</tex>.

|statement= <tex>\mathbb{G' } \setminus U</tex> {{---}} объединение несвязных полных графов.|proof=Пусть это не так, тогда существуют вершины <tex>x,y,z \in \mathbb{V_\mathbb{G'}V} \setminus U</tex>, такие что <tex>xy, yz \in \mathbb{E_\mathbb{GE'}}</tex>, но <tex>xz \notin \mathbb{E_\mathbb{GE'}}</tex>. Так как <tex>y \notin U</tex>, то <tex>\exists t \notin U: yt \notin \mathbb{E_\mathbb{GE'}}</tex>.

В По построению <tex>\mathbb{G'}</tex> в графе <tex>\mathbb{G'}+xz</tex> существует полное паросочетание <tex>M_1</tex>, так как граф <tex>\mathbb{G'}</tex> максимальный по построению. Аналогично, в графе <tex>\mathbb{G'}+yt</tex> существует полное паросочетание <tex>M_2</tex>. Так как в <tex>\mathbb{G'}</tex> нет полного паросочетания, то <tex>xz \in M_1</tex> и <tex>yt \in M_2</tex>.

Построим граф <tex>H</tex>, такой что <tex>\mathbb{V_\mathbb{H}}=\mathbb{V_\mathbb{G'}}=\mathbb{V_\mathbb{G}V}</tex> и <tex>\mathbb{E_\mathbb{H}}=M_1 \oplus M_2</tex>([http://ru.wikipedia.org/wiki/%D1%E8%EC%EC%E5%F2%F0%E8%F7%E5%F1%EA%E0%FF_%F0%E0%E7%ED%EE%F1%F2%FC симметрическая разность]). Получим, что вершины <tex>x,y,z</tex> и <tex>t</tex> лежат на каком-то чередующемся цикле. В силу симметричности <tex>x</tex> и <tex>z</tex> можно считать, что вершины расположены в порядке <tex>tzxy</tex>. Тогда существует путь <tex>P_1=t..zx..y</tex> и полное паросочетание в нем, следовательно существует и путь <tex>P_2=t..zy..x</tex>, содержащий только ребра графа <tex>\mathbb{G'}</tex>. Тогда на пути <tex>x..y</tex> возьмем ребра из паросочетания <tex>M_2</tex>, а на пути <tex>t..z</tex> - ребра из паросочетания <tex>M_1</tex>. Непокрытыми остались вершины <tex>z</tex> и <tex>y</tex>, которые мы покроем ребром <tex>yz</tex>. Вершины, не принадлежащие рассматриваемому циклу, покроем ребрами любого из паросочетаний <tex>M_1, M_2</tex> (выберем ребра одного из них). Таким образом, получили полное паросочетание в графе <tex>\mathbb{G'}</tex>, противоречие.

В каждом из возможных случаев получили противоречие, значит, наше начальное предположение тоже неверно и <tex>\mathbb{G' } \setminus U</tex> {{---}} объединение несвязных полных графов, лемма доказана.