Відкрити головне меню

Зміни

46 байтів додано, 2 місяці тому
нема опису редагування
 
== Доведення ==
Припустимо існує шлях розширення <math>P</math> щодо <Math>M.</math> Розглянемо [[симетрична різниця|симетричну різницю]] <Math>M\oplus P.</math> ОскількиТому що <math>P</math>&nbsp;— єце шляхомшлях розширення щодо <Math>M',</math> <math>M\oplus P</math> також є паруванням в <math>G</math> і <Math>|M\oplus P| = |M| + 1.</math> Отже, протиріччя, тобто <Math>M</math>&nbsp;— є найбільшимнайбільше.
 
Припустимо <math>M</math> не найбільше парування. Нехай <math>M'</math> буде найбільшим паруванням і, відповідно, маємо <math>|M'|>|M|.</math> Розглянемо <math>M\otimesoplus M'.</math> Кожна вершина в <math>M\otimesoplus M'</math> має не більше двох сусідніх, оскільки і <math>M,</math> і <math>M'</math> можуть додати по одній такій вершині. Згідно з попередньою лемою, <Math>M\timesoplus M'</math> складається з циклів парної кількості ребер, шляхів та ізольованих вершин. Отже <math>M</math> може мати більше ребер більше <Math>M'</math> тільки завдяки шляхам. Отже, існує не менше одного шляху в <math>M\timesoplus M',</math> який має більше з <math>M'</math> ніж з <math>M.</math> Але такий шлях є шляхом розширення для <Math>M.</math>
 
== Посилання ==
9472

редагування