Лема Берже

У теорії графів, лема Берже стверджує, що парування $M$ є найбільшим тоді і тільки тоді, якщо в $G$ немає шляхів розширення щодо $M.$

Допоміжна лема

Розглянемо граф $G$ і припустимо, що $M$ і $M'$ є двома паруваннями в $G.$ Нехай $G'$ буде графом отриманим у висліді взяття симетричної різниці $M$ і $M';$ тобто $(M-M')\cup (M'-M).$ $G'$ складатиметься із компонент зв'язності, кожна з яких належить до одного з таких класів:

Ізольована вершина.
Парний цикл чиї ребра чергуються між $M$ і $M'.$
Шлях чиї ребра чергуються між $M$ і $M',$ який не є циклом.

Цю лему можна довести звернувши увагу на те, що кожна вершина в $G'$ може бути інцидентна не більше ніж двом ребрам: одному з $M$ і одному з $M'.$ Графи чиї вершини мають степені, що менші або дорівнюють 2, повинні складатись з або ізольованих вершин, або циклів, або шляхів. Більше того, кожний шлях і цикл у $G'$ повинен перемежовувати ребра між $M$ і $M'.$ Для того, щоб цикл відповідав цій умові, він мусить мати однакову кількість ребер з $M$ і $M',$ тобто парну кількість ребер.

Доведення

Припустимо існує шлях розширення $P$ щодо $M.$ Розглянемо симетричну різницю $M\oplus P.$ Тому що $P$ — це шлях розширення щодо $M',$ $M\oplus P$ також є паруванням в $G$ і $|M\oplus P|=|M|+1.$ Отже, протиріччя, тобто $M$ — найбільше.

Припустимо $M$ не найбільше парування. Нехай $M'$ буде найбільшим паруванням і, відповідно, маємо $|M'|>|M|.$ Розглянемо $M\oplus M'.$ Кожна вершина в $M\oplus M'$ має не більше двох сусідніх, оскільки і $M,$ і $M'$ можуть додати по одній такій вершині. Згідно з попередньою лемою, $M\oplus M'$ складається з циклів парної кількості ребер, шляхів та ізольованих вершин. Отже $M$ може мати більше ребер більше $M'$ тільки завдяки шляхам. Отже, існує не менше одного шляху в $M\oplus M',$ який має більше з $M'$ ніж з $M.$ Але такий шлях є шляхом розширення для $M.$