Изменения

|statement=Пусть [[Двудольные_графы_и_раскраска_в_2_цвета|двудольный граф ]] <tex>G</tex> содержит единственное [[Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольных_графах#Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольном_графе|полное паросочетание ]] <tex>M</tex>. Тогда можно упорядочить вершины левой <tex>(a_i \in A)</tex> и правой <tex>(b_i \in B)</tex> долей таким образом, что <tex>\forall j > i : (a_i b_j) \notin G</tex>. При этом рёбра паросочетания будут иметь вид <tex>(a_i b_i)</tex>.

Пусть <tex>|A|=n>1</tex> (для <tex>|A|=n-1</tex> утверждение верно). Возьмем произвольную вершину в левой доли. Будем строить из неё [[Теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|чередующуюся цепь]], добавляя по очереди ребро, входящее в <tex>M</tex>, и ребро, не входящее в <tex>M</tex>. Заметим, что такой путь не содержит циклов (циклы нечётной длины невозможны, т. к. так как граф двудольный, циклы чётной длины отсутствуют из-за единственности паросочетания). Если последнее добавленное ребро не принадлежит <tex>M</tex>, то присоединим к цепи ребро из <tex>M</tex>, инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из <tex>M</tex> при достижении вершины [[Основные определения теории графов#Степень вершины|степени]] 1. <br/>Таким образом, последнее ребро в цепи имеет вид <tex>(ab) \in M</tex>, где <tex>a \in A, b \in B, \deg b = 1</tex>. Положим <tex>a_n=a, b_n=b</tex>. Для <tex>G \setminus \{a_n \cup b_n \}</tex> утверждение верно по предположению индукции. С другой стороны, т. к. так как <tex>\deg b_n = 1</tex>, то <tex>(a_i b_n) \notin G</tex> при <tex>i<n</tex>, поэтому для <tex>j = n</tex> утверждение также верно.<br/>

Требуется доказать, что <tex>B</tex> независимо. Предположим обратное. Пусть <tex>B \notin I</tex>, тогда существует [[Теорема о циклах|цикл]] <tex>C \subset B</tex>.<br/> Выберем минимальное <tex>i</tex> такое, что <tex>z_i \in C</tex>. Т. к. Так как <tex>\forall j > i : (y_i z_j) \notin G_M(A)</tex>, то <tex>A \setminus y_i \cup z_j \notin I</tex>, следовательно, <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle </tex>. По [[Оператор замыкания для матроидов#theorem|свойствам замыкания 1 и 3]] получаем:<br/>

Т. к. Так как <tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>, то <tex>A \setminus y_i \cup z_i \notin I</tex>, т. е. то есть в <tex>G_M(A)</tex> не существует ребра <tex>(y_i z_i)</tex>. Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.