Lemma a kézfogásokról

A kézfogási lemma a gráfelmélet egy olyan pozíciója , amely szerint bármely véges irányítatlan gráfnak páros számú páratlan fokú csúcsa van . Az elnevezés egy jól ismert matematikai feladatból ered: be kell bizonyítani, hogy bármely csoportban páros azoknak a száma, akik páratlan számú emberrel kezet fogtak.

A lemma a hatványösszeg képlet következménye , amelyet néha kézfogási lemmának is neveznek :

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

sok csúcsú és sok élű gráfhoz . Mindkét eredményt igazolta Euler a königsbergi hét hídról szóló jelentésében (1736), amely a gráfelméleti kutatás kezdetét jelentette. $V$ $E$

A gráf páratlan fokú csúcsait néha páratlan csúcsoknak vagy páratlan csomópontoknak nevezik ; Ezzel a terminológiával a lemma a következőképpen fogalmazható meg: minden gráfnak páros számú páratlan csúcsa van.

A hatványösszeg képletből következik, hogy - a csúcsok számával rendelkező szabályos gráfnak vannak élei [1] ; különösen, ha páratlan, akkor az élek számának oszthatónak kell lennie -vel . $k$ $n$ $kn/2$ $k$ $k$

A lemma nem vonatkozik a végtelen gráfokra , még akkor sem, ha véges számú páratlan csúcsuk van. Például egy végtelen útvonalnak egy végpontjával egyetlen páratlan csúcsa van (azaz egy páratlan szám).

A lemmát Sperner lemmájának egyik bizonyítására használják , valamint a „ hegymászás problémájában ”.

Bizonyítás

A hatványok megfogalmazásakor Euler a kettős (ismételt) számlálás technikáját használta: megszámolta az incidens párok számát , ahol egy él és annak egyik végcsúcsa kétféle módon. Él hozzáadásakor a gráf csúcsainak fokszámainak összege 2-vel nő, vagyis a csúcs párokhoz tartozik , ahol a csúcs foka (a rá eső élek száma). Ezért az eseménypárok száma megegyezik az összes hatvány összegével. Azonban minden él két incidens párhoz tartozik, mivel két végpontja van. Ezért az eseménypárok száma egyenlő . Mivel ez a két képlet ugyanarra a halmazra vonatkozik, jelentésük ugyanaz. ${\megjelenítési stílus (v,e)}$ $e$ $v$ $v$ $\deg(v)$ $\deg(v)$ $2|E|$

Az, hogy az egész számok összege páros vagy páratlan , nem függ a páros tagok számától. Az összeg páros, ha a páratlan tagok száma páros (és egyébként páratlan). Mivel az egyenlet egyik része mindig páros , a másik részének páros számú páratlan tagot, azaz páratlan fokú csúcsot kell tartalmaznia. $(2|E|)$

Jegyzetek

↑ Oldes, Joan M. & Wilson, Robin J. (2000), 2.2. Tétel, Grafikonok és alkalmazások: Bevezető megközelítés , Matematika egyetemi sorozat, Nyílt Egyetem, Springer-Verlag, o. 44, ISBN 978-1-85233-259-4

Irodalom

Cameron, Cathy & Edmonds, Jack (1999), Néhány páratlan számú páratlan csomópont grafikus felhasználása , Annales de l'Institut Fourier 49. kötet (3): 815–827 , < http://www.numdam.org/ item?id=AIF_1999__49_3_815_0 > .
Euler, L. (1736), Solutio problematis ad geometriam situs pertinentis , Commentarii Academiae Scientiarum Imperialis Petropolitanae T. 8 : 128–140 , < http://math.dartmouth.edu/~euler/docs/originals/E053.pdf . Nyomtatás és fordítás: Biggs, N. L.; Loyd, I. K. & Wilson, R. J. (1976), Graph Theory 1736–1936 , Oxford University Press .
Papadimitriou, Christos H. (1994), A paritásérv összetettségéről és a létezés egyéb nem hatékony bizonyítékairól , Journal of Computer and System Sciences, 48. kötet (3): 498–532 , DOI 10.1016/S0022-0000(05)80063 -7 .
Thomason, A. J. (1978), Hamilton-ciklusok és egyedi élű színes gráfok , Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , vol. 3, Annals of Discrete Mathematics, p. 259–268 , DOI 10.1016/S0167-5060(08)70511-9 .