Изменения
Нет описания правки
==Теорема==
Докажем оригинальную версию теоремы, доказанную независимо Самнером (''Sumner'', 1974) и Лас Вергнасом (''Las Vergnas'', 1975). Напомним, что индуцированный подграф <tex>-</tex> это граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
{{Теорема
|proof=
:Докажем теорему по индукции.
:Теорема довольно просто проверяется для случаев <tex>n = 2, 3</tex>. Предположим, что теорема выполняется для <tex>n - 1</tex> (<tex>n \geq 4</tex>). Пусть <tex>G</tex> — связный граф порядка <tex>2n</tex> и предположим, что <tex>k</tex> <tex>-</tex> это такое число, что любой индуцированный связный подграф <tex>G</tex> четного порядка <tex>2k</tex> содержит совершенное паросочетание. Напомним, что индуцированный подграф <tex>-</tex> это граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества
:Случай <tex>k = n</tex> очевиден, поэтому можно считать, что <tex>k \leq n - 1</tex>.
:Если граф содержит смежные листы <tex>a</tex> и <tex>b</tex>, то рассмотрим любой связный подграф графа <tex>G</tex> четного порядка <tex>2k</tex>, содержащий эти вершины. Тогда хотя бы одна из вершин <tex>a, b</tex> будет не покрыта паросочетанием.
