Лемма о рукопожатиях
Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других людей, чётно.
Лемма является следствием формулы суммы степеней, также иногда называемой леммой о рукопожатиях:
- [math]\displaystyle{ \sum_{v\in V} \deg(v) = 2|E| }[/math]
для графа с множеством вершин [math]\displaystyle{ V }[/math] и множеством рёбер [math]\displaystyle{ E }[/math]. Оба результата доказаны Эйлером в докладе о семи мостах Кёнигсберга (1736), положившем начало исследованиям в области теории графов.
Вершины нечётных степеней графа иногда называются нечётными вершинами или нечётными узлами; используя эту терминологию, можно перефразировать лемму таким образом: каждый граф имеет чётное число нечётных вершин.
Формула суммы степеней подразумевает, что [math]\displaystyle{ k }[/math]-регулярный граф с числом вершин [math]\displaystyle{ n }[/math] имеет [math]\displaystyle{ kn/2 }[/math] рёбер[1]; в частности, если [math]\displaystyle{ k }[/math] нечётно, число рёбер должно делиться на [math]\displaystyle{ k }[/math].
Лемма неприменима к бесконечным графам, даже если они имеют конечное число нечётных вершин. Например, бесконечный путь с одной концевой вершиной имеет единственную нечётную вершину (то есть, нечётное количество).
Лемма использована в одном из доказательств леммы Шпернера, а также «задачи о восхождении на гору».
Доказательство
При формулы степеней Эйлер использовал технику двойного (повторного) счёта: посчитал количество инцидентных пар [math]\displaystyle{ (v,e) }[/math], где [math]\displaystyle{ e }[/math] — ребро и [math]\displaystyle{ v }[/math] — одна из его концевых вершин двумя разными способами. При добавлении ребра сумма степеней вершин графа увеличивается на 2, то есть вершина [math]\displaystyle{ v }[/math] принадлежит [math]\displaystyle{ \deg(v) }[/math] парам, где [math]\displaystyle{ \deg(v) }[/math] — степень вершины (количество инцидентных ей рёбер). Следовательно, число инцидентных пар совпадает с суммой всех степеней. Однако каждое ребро принадлежит двум инцидентным парам, так как имеет две концевые вершины. Поэтому число инцидентных пар равно [math]\displaystyle{ 2|E| }[/math]. Поскольку две данные формулы предназначены для одного и то же множества, их значения одинаковы.
Чётность или нечётность суммы целых чисел не зависит от количества чётных слагаемых. Сумма чётна, если число нечётных слагаемых чётно (и нечётна в противном случае). Так как одна часть уравнения всегда чётна [math]\displaystyle{ (2|E|) }[/math], другая часть должна содержать чётное число нечётных слагаемых, то есть вершин нечётной степени.
Примечания
- ↑ Олдес, Джоан M. & Уилсон, Робин Дж. (2000), Theorem 2.2, Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, с. 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, <http://www.numdam.org/item?id=AIF_1999__49_3_815_0>.
- Эйлер, Л. (1736), Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae Т. 8: 128–140, <http://math.dartmouth.edu/~euler/docs/originals/E053.pdf>. Печать и перевод: Биггз, Н. Л.; Лойд, И. 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.
- Томасон, A. Дж. (1978), Hamiltonian cycles and uniquely edge colourable graphs, Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), vol. 3, Annals of Discrete Mathematics, с. 259–268, DOI 10.1016/S0167-5060(08)70511-9.