Изменения

Упорядочим вершины левой <tex>(y_i \in A \setminus B)</tex> и правой <tex>(z_j \in B \setminus A)</tex> долей таким образом, что <tex>\forall j > i : \langle y_i, z_j \rangle \notin G_M(A)</tex>. При таком упорядочивании ребра паросочетания имеют вид <tex> \langle y_i, z_i \rangle</tex>.:Требуется доказать, что <tex>B</tex> независимо. :Предположим обратное. Пусть <tex>B \notin I</tex>, тогда . Tогда существует [[Теорема о циклах|цикл]] <tex>C \subset B</tex>.<br/> Выберем минимальное <tex>i</tex> такое, что <tex>z_i \in C</tex>. Так как <tex>\forall j > i : (\langle y_i , z_j) \rangle \notin G_M(A)</tex>, то <tex>A \setminus y_i \cup z_j \notin I</tex>, следовательно. Cледовательно, <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle </tex>.  :По [[Оператор замыкания для матроидов#theorem|свойствам замыкания 1 и 3]] получаем:<br/>

Так как <tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>, то <tex>A \setminus y_i \cup z_i \notin I</tex>, то есть в <tex>G_M(A)</tex> не существует ребра <tex>(\langle y_i , z_i)\rangle</tex>. :Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.