Изменения

Утверждается, что для всех <tex>i : |I_i \cap T| = r_i(T)</tex>(что означает, что <tex>I_i \cap T</tex> - максимальное подмножество <tex>T</tex>, независимое в <tex>M_i</tex>). Предположим, что это не так. <tex>|I_i \cap T| = r_i(I_i\cap T) <= \le r_i(T)</tex>, это возможно только если <tex>|I_i \cap T| < r_i(T)</tex>. Значит существует такой <tex>x \in T \cap (S \setminus I_i)</tex>, для которого <tex>(I_i \cap T) + x \in J_i</tex>. Но <tex>x \notin F</tex> по предположению вначале доказательства, значит <tex>I_i + x \notin J_i</tex>. Из этого следует, что <tex>I_i + x</tex> содержит единственный цикл. Значит существует <tex>y \in I_i - T</tex>, такой что <tex>I_i + x - y \in J_i</tex>. Получается, что <tex>(y, x)</tex> - ребро в <tex>D_{M_i}(I_i)</tex> и оно содержит этот <tex>y \in T</tex>, что противоречит тому как был выбран <tex>y \in I_i \setminus T</tex>. Следовательно для всех <tex>i</tex> нам известно : <tex>|I_i \cap T| = r_i(T \cap S_i)</tex>.У нас есть <tex>s \in T</tex> и <tex>(I + s) \cap T = (\cup I_i + s)\cap T = \cup(I_i \cap T) + s</tex>. Из определния функции ранга объединения матроидов имеем : <tex>r_M(I + s) <= \le (|(I + s)\setminus T| + \sum _{k=1}^{n}r_i(T))</tex><tex>r_M(I + s) <= \le |(I + s)\setminus T| + \sum _{k=1}^{n} |I_i \cap T| = |I\setminus T| + \sum _{k=1}^{n} |I_i \cap T| = |I| < |I + s|</tex> и значит <tex>(I + s) \notin J</tex> - противоречие.