Изменения

Пусть <tex>G(V,E)</tex> {{---}} [[Основные_определения_теории_графов#Двудольный_граф |двудольный граф]] . <tex>L</tex> {{---}} множество вершин первой доли. <tex>R</tex> {{---}} множество вершин правой доли.

|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' <tex>X</tex> ''(англ. neighborhood)'' определим формулой: <tex>N(X)= \{ y \in V: \mid (x,y) \in E , x \in X\}</tex>

Очевидно, что если существует полное паросочетание, то для любого <tex>A \subset L </tex> выполнено <tex>|A| \leqslant |N(A)|</tex>. У любого подмножества вершин есть по крайней мере столько же "''соседей" '' ("соседи по парасочетанию").