Лема Берже

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

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

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

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

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

Доведення

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

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

Посилання

• (15 вересня 1957), (PDF), Proceedings of the National Academy of Sciences of the United States of America, 43 (9): 842—844, doi:10.1073/pnas.43.9.842, архів оригіналу (PDF) за 24 вересня 2015, процитовано 13 грудня 2014.