Изменения

Пусть дан двудольный граф замен. В его правой доле можно выделить выделено два подмножества вершин <tex>X_1 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_2 \}</tex>. Пусть <tex>P</tex> — кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Рассмотрим сужение <tex>G'</tex> {{---}} сужение графа <tex>G</tex> на множество вершин, лежащих в пути <tex>P</tex>.<br>Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].

Строго говоря, утверждение теоремы не совсем корректно, так :Так как в правой доле полученного графа <tex>G'</tex> вершин на одну больше, чем в левой. Поэтому , добавим в <tex>G'</tex> фиктивную вершину и отнесем ее к левой доле. Пусть путь :Рассмотрим <tex>P = (a_1, b_1, a_2, b_2, \ldots , a_k, b_k)</tex>{{---}} кратчайший путь из условия, где <tex>a_1</tex> — {{---}} фиктивная вершина (рис. 1). :В таком случае, полное паросочетание {{---}} это набор ребер <tex>\langle a_i,b_i \rangle</tex>.

Существование полного паросочетания очевидно — это ребра <tex>(a_i,b_i)</tex>Докажем единственность. Предположим, что :Пусть существует другое паросочетание <tex>(\langle a_i, b_{j_i})\rangle</tex>. Тогда пусть <tex>i_0 = \min \{ i \: \mid \: j_i < i \}</tex>. :Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, что <tex>i_1 < i_0</tex> и поэтому не может быть <tex>j_{i_1} < i_1j_{i_0}</tex>, ведь <tex>i_0</tex> — минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = i_1j_{i_0}</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару. :Следовательно, <tex>j_{i_1} > i_1j_{i_0}</tex> (рис. 2). Это значит, что существует путь <tex>P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )</tex> короче, чем <tex>P</tex>. Противоречие, что противоречит утверждению теоремы.