Лемма о рукопожатиях

Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других людей, чётно.

Чётное число вершин (четыре: 2, 4, 5 и 6) данного графа имеют нечётную степень. Сумма степеней всех вершин равна 14, то есть удвоенному числу рёбер графа.

Лемма является следствием формулы суммы степеней, также иногда называемой леммой о рукопожатиях:

$\sum _{v\in V}\deg(v)=2|E|$

для графа с множеством вершин $V$ и множеством рёбер $E$. Оба результата доказаны Эйлером в докладе о семи мостах Кёнигсберга (1736), положившем начало исследованиям в области теории графов.

Вершины нечётных степеней графа иногда называются нечётными вершинами или нечётными узлами; используя эту терминологию, можно перефразировать лемму таким образом: каждый граф имеет чётное число нечётных вершин.

Формула суммы степеней подразумевает, что $k$-регулярный граф с числом вершин $n$ имеет $kn/2$ рёбер; в частности, если $k$ нечётно, число рёбер должно делиться на $k$.

Лемма неприменима к бесконечным графам, даже если они имеют конечное число нечётных вершин. Например, бесконечный путь с одной концевой вершиной имеет единственную нечётную вершину (то есть, нечётное количество).

Лемма использована в одном из доказательств леммы Шпернера, а также «задачи о восхождении на гору».

Доказательство

При доказательстве формулы степеней Эйлер использовал технику двойного (повторного) счёта: посчитал количество инцидентных пар $(v,e)$, где $e$ — ребро и $v$ — одна из его концевых вершин двумя разными способами. При добавлении ребра сумма степеней вершин графа увеличивается на 2, то есть вершина $v$ принадлежит $\deg(v)$ парам, где $\deg(v)$ — степень вершины (количество инцидентных ей рёбер). Следовательно, число инцидентных пар совпадает с суммой всех степеней. Однако каждое ребро принадлежит двум инцидентным парам, так как имеет две концевые вершины. Поэтому число инцидентных пар равно $2|E|$. Поскольку две данные формулы предназначены для одного и то же множества, их значения одинаковы.

Чётность или нечётность суммы целых чисел не зависит от количества чётных слагаемых. Сумма чётна, если число нечётных слагаемых чётно (и нечётна в противном случае). Так как одна часть уравнения всегда чётна $(2|E|)$, другая часть должна содержать чётное число нечётных слагаемых, то есть вершин нечётной степени.

Литература

• Кэмерон, Кэти; Эдмондс, Джек (1999), "Some graphic uses of an even number of odd nodes", Annales de l'Institut Fourier, 49 (3): 815—827, MR 1703426.
• Эйлер, Л. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128—140. Печать и перевод: Биггз, Н. Л.; Лойд, И. K.; Уилсон, Р. Дж. (1976), Graph Theory 1736–1936, Oxford University Press.
• Пападимитриу, Христос Х. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498—532, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.
• Томасон, A. Дж. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259—268, doi:10.1016/S0167-5060(08)70511-9, MR 0499124.