308
правок
Изменения
м
Нет описания правки
# От противного. Пусть <tex>D = (C_1 \cup C_2) \setminus p</tex> независимо.
#: Обозначим <tex>A = C_1 \cap C_2</tex>. Покажем, что <tex>|A| < |D|</tex>. Из предыдущего пункта очевидным образом следует, что <tex>|C_1 \setminus C_2| > 0</tex> и <tex>|C_2 \setminus C_1| > 0</tex>.
#: <tex>|D| = |C_1 \setminus C_2| + |C_2 \setminus C_1| + |A| - 1 \ge geqslant |A| + 1 + 1 - 1 = |A| + 1 > |A|.</tex>
#: Отсюда путем многократного применения третьей аксиомы матроидов получим <tex>\exists B: A \subset B</tex> и <tex>|B| = |D|</tex>, причем <tex>B</tex> {{---}} независимо.
#: Поскольку <tex>C_1</tex> {{---}} цикл, <tex>C_1 \nsubseteq B</tex>. Значит, найдется хотя бы один элемент в <tex>C_1 \setminus A</tex>, не лежащий в <tex>B</tex>. Следовательно в <tex>B</tex> лежит не более чем <tex>|C_1 \setminus A| - 1</tex> элементов из этого множества. Аналогично в <tex>B</tex> лежит не более чем <tex>|C_2 \setminus A| - 1</tex> элементов из множества <tex>C_2 \setminus A</tex>.
#: Получаем: <tex>|B| \le leqslant |A| + |C_1 \setminus A| - 1 + |C_2 \setminus A| - 1 = |C_1 \cup C_2| - 2 = |D| - 1</tex>. А поскольку <tex>|B| = |D|</tex> получаем противоречие.
}}
