Изменения
Нет описания правки
Радо-Эдмондса
|statement=
<br> Тогда <tex>A \cup x</tex> - множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
|proof=
Рассмотрим <tex>B \in I</tex> - минимальное независимое множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>. <br>Очевидно, что <tex>\exists y \in B\setminus A : A \cup y \in I</tex>.<br>Тогда верны два неравенства:
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) \ge \omega (B)</tex>
<br><tex>\omega (B \ge setminus y) = \omega (B) - \omega (y) \ge \omega (A)</tex><br>Сложим эти два неравенства и получим<br><tex>\omega (A) + \omega (B) \ge \omega (A) + \omega (B) </tex>, что свидетельствует о том, что все знаки в неравенствах можно заменить на равенства.<br>Следовательно<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)</tex>
<br><tex>\omega (A \cup y) = \omega (B)</tex>
<br>Таким образом получаем, что если объединить множество <tex>A</tex> с <tex>x</tex> - минимальным из таких, что <tex>A \cup x \in I</tex>, то получим минимальное независимое множество мощности <tex>k + 1</tex>. Теорема доказана.
}}
