Файл:6n-graf.svgЧётное число вершин (четыре: 2, 4, 5 и 6) данного графа имеют нечётную степень. Сумма степеней всех вершин равна 14, то есть удвоенному числу рёбер графа.
Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других людей, чётно.
Лемма является следствием формулы суммы степеней, также иногда называемой леммой о рукопожатиях:
<math>\sum_{v\in V} \deg(v) = 2|E|</math>
для графа с множеством вершин <math>V</math> и множеством рёбер <math>E</math>. Оба результата доказаны Эйлером в докладе о семи мостах Кёнигсберга (1736), положившем начало исследованиям в области теории графов.
Вершины нечётных степеней графа иногда называются нечётными вершинами или нечётными узлами; используя эту терминологию, можно перефразировать лемму таким образом: каждый граф имеет чётное число нечётных вершин.
Формула суммы степеней подразумевает, что <math>k</math>-регулярный граф с числом вершин <math>n</math> имеет <math>kn/2</math> рёбер[1]; в частности, если <math>k</math> нечётно, число рёбер должно делиться на <math>k</math>.
Лемма неприменима к бесконечным графам, даже если они имеют конечное число нечётных вершин. Например, бесконечный путь с одной концевой вершиной имеет единственную нечётную вершину (то есть, нечётное количество).
При формулы степеней Эйлер использовал технику двойного (повторного) счёта: посчитал количество инцидентных пар <math>(v,e)</math>, где <math>e</math> — ребро и <math>v</math> — одна из его концевых вершин двумя разными способами. При добавлении ребра сумма степеней вершин графа увеличивается на 2, то есть вершина <math>v</math> принадлежит <math>\deg(v)</math> парам, где <math>\deg(v)</math> — степень вершины (количество инцидентных ей рёбер). Следовательно, число инцидентных пар совпадает с суммой всех степеней. Однако каждое ребро принадлежит двум инцидентным парам, так как имеет две концевые вершины. Поэтому число инцидентных пар равно <math>2|E|</math>. Поскольку две данные формулы предназначены для одного и то же множества, их значения одинаковы.
Чётность или нечётность суммы целых чисел не зависит от количества чётных слагаемых. Сумма чётна, если число нечётных слагаемых чётно (и нечётна в противном случае). Так как одна часть уравнения всегда чётна <math>(2|E|)</math>, другая часть должна содержать чётное число нечётных слагаемых, то есть вершин нечётной степени.
