Теорема Бержа

Формулировка. Паросочетание является максимальным тогда и только тогда, когда не существует увеличивающих относительно него цепей.

Доказательство необходимости. Покажем, что если паросочетание   максимально, то не существует увеличивающей относительно него цепи. Доказательство это будет конструктивным: мы покажем, как увеличить с помощью этой увеличивающей цепи   мощность паросочетания   на единицу.

Для этого выполним так называемое чередование паросочетания вдоль цепи  . Мы помним, что по определению первое ребро цепи   не принадлежит паросочетанию, второе — принадлежит, третье — снова не принадлежит, четвёртое — принадлежит, и т.д. Давайте поменяем состояние всех рёбер вдоль цепи  : те рёбра, которые не входили в паросочетание (первое, третье и т.д. до последнего) включим в паросочетание, а рёбра, которые раньше входили в паросочетание (второе, четвёртое и т.д. до предпоследнего) — удалим из него.

Понятно, что мощность паросочетания при этом увеличилась на единицу (потому что было добавлено на одно ребро больше, чем удалено). Осталось проверить, что мы построили корректное паросочетание, т.е. что никакая вершина графа не имеет сразу двух смежных рёбер из этого паросочетания. Для всех вершин чередующей цепи  , кроме первой и последней, это следует из самого алгоритма чередования: сначала мы у каждой такой вершины удалили смежное ребро, потом добавили. Для первой и последней вершины цепи   также ничего не могло нарушиться, поскольку до чередования они должны были быть ненасыщенными. Наконец, для всех остальных вершин, — не входящих в цепь  , — очевидно, ничего не поменялось. Таким образом, мы в самом деле построили паросочетание, и на единицу большей мощности, чем старое, что и завершает доказательство необходимости.

Доказательство достаточности. Докажем, что если относительно некоторого паросочетания   нет увеличивающих путей, то оно — максимально.

Доказательство проведём от противного. Пусть есть паросочетание  , имеющее бОльшую мощность, чем  . Рассмотрим симметрическую разность   этих двух паросочетаний, т.е. оставим все рёбра, входящие в   или в  , но не в оба одновременно.

Понятно, что множество рёбер   — уже наверняка не паросочетание. Рассмотрим, какой вид это множество рёбер имеет; для удобства будем рассматривать его как граф. В этом графе каждая вершина, очевидно, имеет степень не выше 2 (потому что каждая вершина может иметь максимум два смежных ребра — из одного паросочетания и из другого). Легко понять, что тогда этот граф состоит только из циклов или путей, причём ни те, ни другие не пересекаются друг с другом.

Теперь заметим, что и пути в этом графе   могут быть не любыми, а только чётной длины. В самом деле, в любом пути в графе   рёбра чередуются: после ребра из   идёт ребро из  , и наоборот. Теперь, если мы рассмотрим какой-то путь нечётной длины в графе  , то получится, что в исходном графе   это будет увеличивающей цепью либо для паросочетания  , либо для  . Но этого быть не могло, потому что в случае паросочетания   это противоречит с условием, а в случае   — с его максимальностью (ведь мы уже доказали необходимость теоремы, из которой следует, что при существовании увеличивающей цепи паросочетание не может быть максимальным).

Докажем теперь аналогичное утверждение и для циклов: все циклы в графе   могут иметь только чётную длину. Это доказать совсем просто: понятно, что в цикле рёбра также должны чередоваться (принадлежать по очереди то  , то  ), но это условие не может выполниться в цикле нечётной длины — в нём обязательно найдутся два соседних ребра из одного паросочетания, что противоречит определению паросочетания.

Таким образом, все пути и циклы графа   имеют чётную длину. Следовательно, граф   содержит равное количество рёбер из   и из  . Но, учитывая, что в   содержатся все рёбра   и  , за исключением их общих рёбер, то отсюда следует, что мощность   и   совпадают. Мы пришли к противоречию: по предположению паросочетание   было не максимальным, значит, теорема доказана.