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

Определения

Пусть [math]G(V,E)[/math] - двудольный граф.

Определение:

Полным(совершенным) паросочетанием называется паросочетание в которое входят все вершины.

Определение:

Пусть [math]X \subset V [/math]. Множeством соседей [math]N(X)= {y \in V: (x,y) \in E }[/math]

Теорема

Теорема (Холл):

абацаба

Доказательство:

[math]\triangleright[/math]

доказательство (необязательно)

[math]\triangleleft[/math]