Изменения

* Переход

*: Пусть <tex>k = |A| = |B|</tex>.

*:Рассмотрим матроид <tex>M_1 = \langle X, \{ A \mid A \in I, A \leq k \} \rangle</tex>. Множества <tex>A, B \in I</tex> и <tex>|A| = |B|</tex>, а значит они являются базами для матроида <tex>M_1</tex>. Тогда по [[Теорема о базах|теореме о базах]] <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y

\in I</tex>, поэтому <tex>(x, y) \in G_M(A)</tex>. Множества <tex>A' = A - x + y </tex> и <tex>B' = B + x - y</tex> являются независимыми как подмножества независимых и их <tex>|A' \bigtriangleup B'| < |A \bigtriangleup B|</tex> Тогда по предположению индукции на их <tex>| A' \bigtriangleup B'|</tex> есть полное паросочетание <tex>N</tex>. Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>, а значит индукционный переход справедлив.