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

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

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

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

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

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