Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем

Лемма:

Пусть дан двудольный граф [math]G(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}[/math] — граф замен. В его правой доле можно выделить два подмножества вершин [math]X_1 = \{z \in S \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I | I \cup z \in I_2 \}[/math]. Пусть [math]P[/math] - кратчайший путь из [math]X_1[/math] в [math]X_2[/math]. Рассмотрим сужение [math]G'[/math] графа [math]G[/math] на множество вершин, лежащих в пути [math]P[/math]. Тогда в [math]G'[/math] существует единственное полное паросочетание.