Лема Берже

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

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

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

1. Ізольована вершина.
2. Парний цикл чиї ребра чергуються між $M$ і $M^{\prime }.$
3. Шлях чиї ребра чергуються між $M$ і $M^{\prime },$ який не є циклом.

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

Доведення

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

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

Посилання

• Шаблон:Citation.