Изменения

В графе <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>x,z</tex> и <tex>y,t</tex> лежат в разных полных подграфах графа <tex>\mathbb{G'} \setminus U</tex>, обозначим их <tex>H_1</tex> и <tex>H_2</tex>, соответственно.

Покроем вершины подграфа <tex>H_1</tex> паросочетанием <tex>M_2</tex>, при этом заметим, что ребро <tex>xz</tex> не входит в это паросочетание. Аналогично покроем паросочетанием <tex>M_1</tex> вершины подрафа <tex>H_2</tex> и ребро <tex>yt</tex> не войдет в это паросочетание. Если остались непокрытые вершины, то покроем их ребрами из любого паросочетания <tex>M_1</tex> или <tex>M_2</tex>. Таким образом, мы получим полное паросочетание в графе <tex>\mathbb{G'}</tex>, что противоречит его построению.