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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• Кэмерон, Кэти; Эдмондс, Джек (1999), , , 49 (3): 815—827, MR .
• Эйлер, Л. (1736), (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 : , MR .
• Томасон, 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 : , MR .