[[Файл:6n-graf.svg|thumb|250px|На цьому графі, з парним числом вершин (чотири вершини пронумеровані 2, 4, 5 і 6) мають непарні ступеняступені. Сума ступенів вершин дорівнює 2 + 3 + 2 + 3 + 3 + 1 = 14, подвійному числу ребер.]]
У [[теорія графів|теорії графів]], галузі [[Математика|математики]], '''Лема про рукотисканнярукостискання''' є твердженням, що у кожного кінцевого ненаправленного[[Граф_(математика)#Орієнтований графаграф|неорієнтованого графу]] є парне число вершин з непарним [[Степінь вершини (теорія графів)|степенем]] (число граней, що торкаються[[Словник_термінів_теорії_графів#І|інцидентні]] вершинивершині). Якщо простіше, у группігрупі людей, деякі з якихякі обмінюються рукостисканнямрукостисканнями, парне число людей, мабуть,напевно потиснули непарненепарну числокількість рук інших людей.
Лема про рукотисканнярукостискання — наслідок формули суми ступенейступенів (яку також іноді називають '''лемою про рукотисканнярукостискання''').
: <math>\sum_{v\in V} \deg(v) = 2|E|</math>
для графа з безліччюмножиною [[Вершина (теорія графів)|вершин]] ''V'' і множиною ребер ''Е''. Обидва результати довів [[Леонард Ейлер]] (1736) у своїй знаменитій роботі про [[Сім мостів Кеніґсберґа]], яказ розпочалаякої вивченняпочинається [[теорія графів|теорії графів]].
Вершини непарного степеня в графі іноді називають '''непарними вузлами''' або '''непарними вершинами'''; в цій термінології, лему про рукотисканнярукостискання можна переформулювати як твердження, що кожен граф має парне число непарних вузлів.
== Доказ ==
Доказ формули суми ступенейступенів Ейлера використовує техніку подвійного підрахунку: він підраховує кількість інцидентних пар (''v'', ''e''), де '''e''' — ребро, і вершина '''v''' є одним з його кінців у двох різних кінцях. Вершина ''v'' належить до пар deg(''v''), де deg(''v'') ([[Степінь вершини (теорія графів)|степыньстепінь вершини]] ''v'') — кількість ребер, інцидентних їй. Тому число інцидентних пар є сумою степенів. Тим не менш, кожне ребро в графі належить саме двом парам інциденту, по одному для кожної з його кінців; Тому, число інцидентних пар — 2|E|. Так як ці дві формули розраховують один й той же набір об'єктів, вони повинні мати однакові значення.
У сумі чисел, [[Парність (математика)|парність]] суми не впливає навіть на доданки у сумі; загальна сума є парною, якщо є парне число непарних точок, і непарною, коли є непарне число непарних членів. Так як одна частина формули суми ступенейступенів є парним числом 2|E|, сума на іншій стороні повинна бути парним числом непарних членів; тобто, повинно бути парне число вершин з непарним степенем.
В якості альтернативи можна використовувати [[Математична індукція|математичну індукцію]], щоб довести, що число вершин з непеарнимнепарним степенем є парним, шляхом видалення одного ребра з цього графу і одночасно використати аналіз випадків на ступенях його кінцевих точок, щоб визначити вплив видалення парності числа непарного степеня вершин.
== Регулярні графи ==
== Нескінченні графи ==
[[Файл:Infinite graph one direction.svg|thumb|150px|Нескінченний граф, який не підкорюється лемі про рукотисканнярукостискання]]
Лема про рукотисканнярукостискання не поширюється на нескінченні графи, навіть якщо вони мають кінцеве число вершин з непарним степенем. Наприклад, нескінченний [[Шлях (теорія графів)|шлях]] графа з однієї кінцевої точки має тільки одну вершину з непарним степенем замість парного число таких вершин.
== Обмін графів ==
Кілька комбінаторних структур, перечисленихнаведених Кемероном і Едмондсом ({{harvtxt|Cameron|Edmonds|1999}}), можуть бути показаними навіть у ряді зв'язавши їх з непарними вершинами у відповідному «обміну графа».
Наприклад, як С. Сміт довів, в будь-якому [[Кубічний граф|кубічному графі]] G має бути парне число [[Гамільтонів граф|гамільтонових циклів]] через будь-яку фіксовану ''uv''; Томасон у 1978 використав доказ, заснований на лемі рукостискання, аби розширити цей результат графів, в якимуякому всі вершини мають непарну ступінь. Томасон визначає графік обміну ''H'', вершини якого знаходяться в відповідності один-до-одного із гамильтоновим шляхом, починаючи з ''u'' і продовжуючи через ''v''. Два таких шляхи ''p''<sub>1</sub> і ''p''<sub>2</sub> з'єднані ребром в H, якщо можна отримати ''p''<sub>2</sub> шляхом додаванням нового ребра до кінця ''p''<sub>1</sub> і видалення іншого ребра з середини ''p''<sub>1</sub>; це [[симетричне відношення]], тобто ''Н'' — неорієнтований граф. Якщо шлях р закінчується у вершині W, то вершина, відповідна р в Н має ступінь, рівний кількості способів, у які р може бути продовжений по кребру, що не пов'язує його назад з u; тобто, ступінь цієї вершини в Н або grad(W) — 1 (парне число), якщо р не є частиною циклу ГамфльтонаГамільтону через uv, або grad(W) — 2 (непарне число), якщо р є частиною циклу Гамільтона через uv. Так як H має парне число непарних вершин, G повинен мати парне число гамільтонових циклів через uv.
== Обчислювальна складність ==
У зв'язку з тим, що спосіб обміну графів для доказу існування комбінаторних структур, представляє інтерес, постає питання, наскільки ефективно ці структури можуть бути знайдені. Наприклад, припустимо, вона данзадана у якості введення гамільтонового циклу в кубічноийкубічний граф; з теореми Сміта випливає, що існує другий цикл. Як швидко можна можна знайти другий цикл? Професор [[Христос Пападімітріу]] досліджував [[Теорія складності обчислень|обчислювальну складність]] питань, такі як це, або в більш загальному вигляді знаходження другої вершини з непарним степенем, коли один отримує одиночну непарну вершину у великому неявному графі. Він визначив [[Обчислювальна складність|обчислювальну складність]] PPA для інкапсуляції таких проблем, як ця.
== Примітки ==
|