Теорема Холла

Для того, чтобы в двудол.графе существовало остовное паросочетание, необх.и дост., чтобы для люб.е паросочетание А1 А выполнялось |Г(А1)|> =|А1|.Док-во: 1)Пусть остов.паросоч.сущ. Если Г‘(А1)-число смеж.верш.из паросочетаний, то вып-ся св-во |Г(А1)’|> =|A1|.Значит, в исх.графе |Г(А1)|> =|Г’(А1)|=|A1|.2)Пусть указ-е св-во вып-ся т.е. для люб. А1 А |Г(А1)|> =|A1|

Док-ть, что сущ. Ост-е парос-е Индукция по числу вершин |A|=|B|=1

Пусть это доказано для |A|=|B|< n Рассм. Граф у кот-го |A|=|B|=n

Надо разбить на 2 случ. а)для всяк мн-ва А1 А, А1< > А |Г(А1)|> |A1|

здесь будет вып-ся |Г(А1)’|> =|A1| и здесь осталось вершин в А1(n-1) т.е. |A|=|B|< n тогда этослучай доказанный нами по индукции(значит и в оставшейся части остается паросочетание)

Б)Сущ такое мн-во А', А'< > A; |A'|=| Г(А')|
Рассм. Ту часть что осталась(A'')

A''=A-A’ B”=B\Г(А’) возьмем А2 А'' Г''(A2)=Г(А2)∩ B'' (т.е. не вошли в Г(А’))

Берем А2UA’по ус-ю|Г(А2UA’)|≥ |А2UA’| |Г’’(A2)UГ(А')|=|Г’’(A2)|+|Г(А')|т.е. |Г’’(A2)|+|Г(А')|≥ |A2|+|A’| т.к. |Г(А')|=|A’| то Г’’(A2)|≥ |A2| след-но в том, что ост-сь тоже вып-ся св-во