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

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

Пусть [math]M = \langle X,I \rangle [/math] — матроид. Множества [math]A, B \in I[/math] — независимы, причем [math]|A| = |B|[/math]. Тогда двудольный граф [math]D_{M}(I)[/math] содержит полное паросочетание на [math]A \bigtriangleup B[/math].

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

[math]\triangleright[/math]

[math]D_{M}(I)[/math] — это двудольный граф с долями [math]I[/math] и [math]S \setminus I[/math] с рёбрами между [math]y \in I[/math] и [math]x \in S \setminus I[/math] если [math] (I \setminus y) \cup x \in \mathcal{I} [/math] Индукция по [math]|A \bigtriangleup B|[/math]. База В случае, когда [math]|A \bigtriangleup B| = 0 [/math], есть пустое паросочетание. Переход Пусть [math]k = |A| = |B|[/math]. Рассмотрим [math]|A \bigtriangleup B| \geq 1[/math]. Рассмотрим матроид [math]M_1 = \langle X, \{ A | A \in I, A \leq k \} \rangle[/math]. Множества [math]A, B \in I[/math] и [math]|A| = |B|[/math], а значит они являются базами для матроида [math]M_1[/math]. Тогда по теореме о базах [math]\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in I[/math], поэтому [math](x, y) \in G_M(A)[/math]. Множества [math]A' = A - x + y [/math] и [math]B' = B + x - y[/math] являются независимыми как подмножества независимых и их [math]|A' \bigtriangleup B'| \leq |A \bigtriangleup B|[/math] Тогда по предположению индукции на их [math]| A' \bigtriangleup B'|[/math] есть полное паросочетание [math]N[/math]. Тогда [math]N \cup {(x, y)}[/math] составляет полное паросочетание на [math]|A \bigtriangleup B|[/math], а значит индукционный переход справедлив. Утверждение доказано.

[math]\triangleleft[/math]