Лема Берже
У теорії графів, лема Берже стверджує, що парування є найбільшим тоді і тільки тоді, якщо в немає шляхів розширення щодо
Допоміжна лема ред.
Розглянемо граф і припустимо, що і є двома паруваннями в Нехай буде графом отриманим у висліді взяття симетричної різниці і тобто складатиметься із компонент зв'язності, кожна з яких належить до одного з таких класів:
- Ізольована вершина.
- Парний цикл чиї ребра чергуються між і
- Шлях чиї ребра чергуються між і який не є циклом.
Цю лему можна довести звернувши увагу на те, що кожна вершина в може бути інцидентна не більше ніж двом ребрам: одному з і одному з Графи чиї вершини мають степені, що менші або дорівнюють 2, повинні складатись з або ізольованих вершин, або циклів, або шляхів. Більше того, кожний шлях і цикл у повинен перемежовувати ребра між і Для того, щоб цикл відповідав цій умові, він мусить мати однакову кількість ребер з і тобто парну кількість ребер.
Доведення ред.
Припустимо існує шлях розширення щодо Розглянемо симетричну різницю Тому що — це шлях розширення щодо також є паруванням в і Отже, протиріччя, тобто — найбільше.
Припустимо не найбільше парування. Нехай буде найбільшим паруванням і, відповідно, маємо Розглянемо Кожна вершина в має не більше двох сусідніх, оскільки і і можуть додати по одній такій вершині. Згідно з попередньою лемою, складається з циклів парної кількості ребер, шляхів та ізольованих вершин. Отже може мати більше ребер більше тільки завдяки шляхам. Отже, існує не менше одного шляху в який має більше з ніж з Але такий шлях є шляхом розширення для
Посилання ред.
- Клод Берже (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.