Изменения

Построим граф <tex>H</tex>, такой что <tex>\mathbb{V_\mathbb{H}}=\mathbb{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>M_1</tex> и <tex>M_2</tex>. Рассмотрим подробнее, почему это будет именно так. Ребро <tex>xz</tex> принадлежит паросочетанию <tex>M_1</tex>, значит вершина <tex>y</tex> и какая-то произвольная вершина <tex>v</tex> будут покрыты ребром паросочетания <tex>M_1</tex>, при этом эти ребра не принадлежат паросочетанию <tex>M_2</tex>, но ребра <tex>yt</tex> и <tex>vu</tex>, где <tex>u</tex> {{---}} произвольная вершина, принадлежат <tex>M_2</tex> и не принадлежат <tex>M_1</tex> и так далее. Таким образом и получается чередующийся цикл в графе <tex>H</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>, противоречие.