PROFILPELAJAR.COM

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

↑ Олдес, Джоан M.; Уилсон, Робин Дж. (2000), "Theorem 2.2", Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44, ISBN 978-1-85233-259-4

Литература

Кэмерон, Кэти; Эдмондс, Джек (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.