Лема про рукостискання: відмінності між версіями

Доказ формули суми степенів Ейлера використовує техніку подвійного підрахунку: він підраховує кількість інцидентних пар (''v'', ''e''), де '''e''' — ребро, а вершина '''v''' - це один із його кінців у двох різних кінцях. Вершина ''v'' належить до пар deg(''v''), де deg(''v'') ([[Степінь вершини (теорія графів)|степінь вершини]] ''v'') — це кількість ребер, інцидентних їй. Тому число інцидентних пар є сумою степенів. Тим не менш, кожне ребро в графі належить саме двом парамінцидентним інцидентупарам, по одному для кожного з його кінців. Тому число інцидентних пар — 2|E|. Так як ці дві формули розраховують один і той самий набір об'єктів, вони повинні мати однакові значення.

У сумі чиселОтже, [[Парність (математика)|парність]] суми нецілих впливаєчисел навітьне назалежить доданкивід упарності сумідоданків. Загальна сума є парною, якщо є парне число непарних точок, і непарною, коли є непарне число непарних членів. Зважаючи на те, що одна частина формули суми степенів є парним числом 2|E|, сума на іншій стороні повинна бути парним числом непарних членів. Тобто, повинно бути парне число вершин з непарним степенем.

Кілька комбінаторних структур, наведених Кемероном і Едмондсом ({{harvtxt|Cameron|Edmonds|1999}}), можуть бути показаними навіть у ряді, зв'язавши їх з непарними вершинами у відповідному «обмінуграфі графаобміну».

Наприклад, як довів {{Нп|Седрік Сміт|С. Сміт||Cedric Smith (statistician)}}, у будь-якому [[Кубічний граф|кубічному графі]] ''G'' має бути парне число [[Гамільтонів граф|гамільтонових циклів]], що проходять через будь-яку фіксовану ''uv.'' Томасон у 1978 використав доказ, заснований на лемі рукостискання, аби розширитипоширити цей результат графівна граф ''G'', в якому всі вершини мають непарний степінь. Томасон визначає графікграф обміну ''H'', вершини якого знаходяться ув однозначній відповідності один-до-одного з гамильтоновим шляхом, починаючи з ''u'' і продовжуючи через ''v''. Два таких шляхи ''p''₁ і ''p''₂ з'єднані ребром в H, якщо можна отримати ''p''₂ шляхом додаванням нового ребра до кінця ''p''₁ і видалення іншого ребра з середини ''p''_1, це [[симетричне відношення]], тобто ''Н'' — неорієнтований граф. Якщо шлях ''р'' закінчується у вершині W''w'', то вершина, відповідна ''р'' в ''Н'' має степінь, рівний кількості способів, у якій може бути продовжений по ребру, що не пов'язує його назад з ''u''. Тобто, степінь цієї вершини в ''Н'' або graddeg(W''w'') — 1 (парне число), якщо ''р'' не є частиною циклуГамільтонова Гамільтонуциклу через ''uv'', або graddeg(W''w'') — 2 (непарне число), якщо ''р'' є частиною Гамільтонова циклу Гамільтона через ''uv''. Так як ''H'' має парне число непарних вершин, ''G'' повинен мати парне число гамільтонових циклів через ''uv''.

У зв'язку з тим, що спосіб обміну графів для доказу існування комбінаторних структур представляє інтерес, постає питання, наскільки ефективно ці структури можуть бути знайдені. Наприклад, припустимо, що вона задана як введеннячастина гамільтонового циклу в кубічний граф. Із теореми Сміта випливає, що існує другий цикл. Як швидко можна знайти другий цикл? Професор [[Христос Пападімітріу]] досліджував [[Теорія складності обчислень|обчислювальну складність]] питань, такіподібних як цецьому, або в більш загальному вигляді знаходження другої вершини з непарним степенем, коли один отримує одиночну непарну вершину у великому неявному графі. Він визначив [[Обчислювальна складність|обчислювальну складність]] PPA{{Нп|PPAD|||}} для інкапсуляції таких проблем, як ця.