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