Изменения

Докажем Индукция по индукции для <tex>|A \bigtriangleup B|</tex>.

* '''База*: При <tex>|A|=1</tex> утверждение очевидно. <br/>* '''Переход*: Пусть верно для <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> при достижении вершины [[Основные определения теории графов#Степень вершины|степени]] <tex>1</tex>. <br/>:Таким образом, последнее ребро в цепи имеет вид <tex>(ab) \langle a, b \rangle \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>(\langle a_i , b_n) \rangle \notin G</tex> при <tex>i<n</tex>, поэтому для <tex>j = n</tex> утверждение также верно.<br/>