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

Определения

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

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

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

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

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

Теорема

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

Полное паросочетание существует тогда и только тогда, когда для любого [math]A \subset L [/math] выполнено [math]|A| \leq |N(A)|[/math].

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

[math]\triangleright[/math]

Очевидно, что если существует полное паросочетание, то для любого [math]A \subset L [/math] выполнено [math]|A| \leq |N(A)|[/math]. У любого подмножества вершин есть по крайней мере столько же соседей. В обратную сторону будем доказывать так :

[math]\triangleleft[/math]