31
правка
Изменения
м
→Теорема
:Теорема довольно просто проверяется для случаев <tex>n = 2, 3</tex>. Предположим, что теорема выполняется для <tex>n - 1</tex> (<tex>n \geq 4</tex>). Пусть <tex>G</tex> — связный граф порядка <tex>2n</tex> и предположим, что <tex>k</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> будет не покрыта паросочетанием.
:Таким образом, граф <tex>G</tex> не содержит смежных листов. Тогда из леммы следует, что существуют смежные вершины <tex>x, y</tex>, что граф <tex>G \backslash \{x, y\}</tex> связен.
:По нашему индукционному предположению, граф <tex>G \backslash \{x, y\}</tex> содержит совершенное паросочетание, а значит, добавив ребро <tex>xy</tex>, мы получим совершенное паросочетание для <tex>G</tex>.
