Изменения

|statement= Пусть <tex>M = \langle X,I \rangle </tex> &mdash; матроид. Множества <tex>A, B \in I</tex>{{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>G_M(A) = \D_{ M}(x, yI) | x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.

*: В случае, когда <tex>|A \bigtriangleup B | = \emptyset 0 </tex>, есть пустое паросочетание.

*: Пусть <tex>k = |A| = |B|</tex>. Рассмотрим <tex>|A \bigtriangleup B| \geq 1</tex>. Рассмотрим матроид <tex>M_1 = \langle X, \{ K A | K A \in I, |K| A \leq |A| 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 \setminus ' = A - x + y </tex> и <tex>B \setminus ' = B + x - y</tex> являются независимыми как подмножества независимых и их <tex>|A' \bigtriangleup</tex> имеет меньшую мощность, чем <tex>B'| \leq |A \bigtriangleup B|</tex>. Тогда по предположению индукции на их <tex>| A' \bigtriangleupB'|</tex> есть полное паросочетание, которое вместе с <tex>N</tex>. Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>, а значит индукционный переход справедлив.