Лемма о единственном паросочетании в графе замен

Лемма (о единственном паросочетании графе замен):

Дан матроид [math]M = \langle X,I \rangle [/math]. Пусть двудольный граф [math]G_M(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}[/math] содержит единственное полное паросочетание на [math]A \oplus B[/math], где [math]A\in I[/math] и [math]|A| = |B|[/math]. Тогда [math]B \in I[/math].

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

[math]\triangleright[/math]

Заметим, что т. к. в графе [math]G_M(A)[/math] нет другого паросочетания, то в нем нет циклов четной длины, значит, граф является ациклическим. Упорядочим вершины левой [math](y_i \in A \setminus B)[/math] и правой [math](z_j \in B \setminus A)[/math] долей таким образом, что [math]\forall j \lt i : (y_i z_j) \notin G_M(A)[/math]. Заметим также, что при такой ориентации ребра паросочетания имеют вид [math](y_i z_i)[/math]. Действительно, ребро в первую вершину правой доли может идти только из первой вершины левой доли. Аналогично во вторую вершину правой доли ведет ребро из второй вершины левой доли и, возможно, ребро из первой вершины, которое уже не может быть использовано в паросочетании и т. д. Требуется доказать, что [math]B[/math] независимо. Предположим обратное. Пусть [math]B \notin I[/math], тогда существует цикл [math]C \subset B[/math]. Выберем минимальное [math]i[/math] такое, что [math]C \subset (A \cap B) \cup \{z_1..z_i\}[/math]. Т. к. [math]\forall j \lt i : (y_i z_j) \notin G_M(A)[/math], то [math]A \setminus y_i \cup z_j \notin I[/math], следовательно, [math]C \setminus z_i \subset \langle A \setminus y_i \rangle [/math]. По свойствам замыкания 1 и 2 получаем: [math]C \setminus z_i \subset \langle A \setminus y_i \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle \langle A \setminus y_i \rangle \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math] Т.к. [math]z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math], то [math]A \setminus y_i \cup z_i \notin I[/math], т. е. в [math]G_M(A)[/math] не существует ребра [math](y_i z_i)[/math]. Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.

[math]\triangleleft[/math]