Изменения

Возможны два случая:

Покроем вершины подграфа <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>, что противоречит тому, как мы изначально построили этот граф.

Построим граф <tex>H</tex>, такой что <tex>\mathbb{V_\mathbb{H}}=\mathbb{V_\mathbb{G'}}</tex> и <tex>\mathbb{E_\mathbb{H}}=M_1 \oplus M_2</tex>. Получим, что вершины <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>M_1</tex> и <tex>M_2</tex>. Таким образом, получили полное паросочетание в графе <tex>\mathbb{G'}</tex>, противоречие.

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

== Теорема Татта ==