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

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

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

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

[math]\triangleright[/math]

Индукция по [math]|A \oplus B|[/math]. База индукции очевидна. Покажем, что справедлив и индукционный переход. Рассмотрим матроид [math]M_1 = [/math] < [math] X[/math], { [math]K | K \in I, |K| \leq |A|[/math]}. Поскольку [math]A, B \in I[/math], то по определению [math]\forall x \in A [/math] \ [math]B: \exists y \in B [/math] \ [math]A : A[/math] \ [math]x \cup y \in I[/math], а значит [math](x, y) \in G_M(A)[/math].

[math]\triangleleft[/math]