Изменения

|proof=Доказательство от противного! Рассмотрим изменения, которые мы внесли в М <tex>M</tex> вдоль дополняющей цепи, чтобы получить паросочетание М'. В этой цепи все промежуточные вершины были насыщенными, а концы свободные. После изменения вдоль этой цепи все вершины, лежащие на этой цепи станут насыщенными. Допустим, что из <tex>x</tex> появилась дополняющая цепь относительно M'. Тогда появившаяся дополняющая цепь должна проходить хотя бы через одну из концевых вершин в той дополняющей цепи, относительно которой вносили изменения, поскольку иначе такая же дополняющая цепь была и в паросочетании М<tex>M</tex>. Однако поскольку в паросочетании М <tex>M</tex> концевые вершины не насыщены, то из вершины <tex>x</tex> в паросочетании М <tex>M</tex> есть все равно есть дополняющая цепь. Надо рассмотреть часть дополняющей цепи в М', ограниченную концом текущей дополняющей цепи и концом той дополняющей цепи, вдоль которой вносили изменения, такую что вершина <tex>x</tex> будет промежуточной. Легко заметить что в такой цепи все промежуточные вершины насыщенные, а концы свободны, поэтому она является дополняющей. Значит, мы пришли к противоречию, поскольку в паросочетании М <tex>M</tex> нет дополняющих цепей из вершины <tex>x</tex>.