Kézfogás-lemma
A matematika, azon belül a gráfelmélet területén a kézfogás-lemma vagy kézfogási lemma az az állítás, hogy minden véges irányítatlan gráf páros darab páratlan fokszámú csúccsal rendelkezik (fokszám: a csúcsból kiinduló élek száma). Egy köznapi életből vett példával, ha egy partin néhány ember kezet fog egymással, a páratlan számú emberrel kezet rázók száma páros.

A kézfogás-lemma a (néha szintén kézfogás-lemmának hívott) fokszámösszeg-képlet következménye, miszerint:
,
ha a gráf csúcshalmazát V-vel, élhalmazát E-vel jelöljük. Mindkét eredményt  igazolta a Königsbergi hidak problémáját vizsgáló híres elemzésében, ami a gráfelmélet megalapozásául szolgált.

A páratlan fokszámú csúcsokat néha egyszerűen „páratlan csúcs”-oknak nevezik; ebben a terminológiában a kézfogáslemma úgy is megfogalmazható, hogy minden gráfnak páros számú páratlan csúcsa van.

Bizonyítás
Euler a fokszámösszeg-képletet a kettős leszámlálás nevű technikával bizonyítja: összeszámolja az érintkező (v,e) párosokat, ahol e egy él és a v csúcs az él valamely végpontja, két különböző módon. A v csúcs deg(v) párba tartozik bele, ahol deg(v) (azaz v fokszáma) a csúccsal érintkező élek száma. Tehát az érintkező párok száma a fokszámok összege. Azonban a gráf minden éle 1-1 végpontja révén pontosan két érintkező párba tartozik, ezért az érintkező párok száma 2|E|. Mivel a két képlet ugyanazt a halmazt számlálja meg, értéküknek azonosnak kell lennie.

Egész számok összegzésekor az összeg párosságát nem befolyásolják a páros tagok; a végösszeg akkor páros, ha páros darab páratlan tag van, és akkor páratlan, ha páratlan darab páratlan tag van. Mivel a fokszámösszeg-képlet egyik oldalán a 2|E| páros szám található, bármely oldalon csak páros számú páratlan tag lehet; ezért csak páros darab páratlan fokszámú csúcs létezhet.

Egy másik bizonyítási módszer lehet a teljes indukció, megmutatva, hogy adott gráfból egy él eltávolításával nem juthatunk páratlan darab páratlan fokszámú csúcsot tartalmazó gráfhoz.

Reguláris gráfok
A fokszámösszeg-képletből következik, hogy bármely n csúcsú r-reguláris gráf nr/2 éllel rendelkezik. Ha pedig r páratlan szám, akkor az élek számának oszthatónak kell lennie r-rel.

Végtelen gráfok

A kézfogáslemma nem vonatkozik végtelen gráfokra, még akkor sem, ha csak véges számú páratlan fokszámú csúcsuk van. Például az ábrán látható végtelen útgráf egyetlen páratlan fokszámú csúccsal rendelkezik.

Cseregráfok
A  tanulmányban listázott több kombinatorikai struktúráról megmutatható, hogy páros számosságú, egy megfelelő „cseregráf” (exchange graph) páratlan fokszámú csúcsai segítségével.

Például, ahogy azt Cedric Smith bizonyította, bármely G 3-reguláris gráfban páros számú, a fix uv élen keresztülmenő Hamilton-körnek kell lennie;  a kézfogáslemma segítségével kiterjesztette a bizonyítást olyan gráfokra, ahol az összes csúcs fokszáma páratlan. A Thomason által definiált H cseregráf csúcsai kölcsönösen megfeleltethetők az eredeti gráf u-ban kezdődő és v-ben folytatódó Hamilton-útjainak. Két ilyen út, p1 és p2 akkor vannak H-ban éllel összekötve, ha p2 megkapható p1 végéhez egy él hozzáadásával és a közepéből egy másik eltávolításával; ez szimmetrikus reláció, ezért H irányítatlan gráf. Ha a p út a w csúcsban végződik, akkor H-ban p-nek megfelelő csúcs fokszáma éppen a lehetőségek száma, ahogy p kiterjeszthető u-ba vissza nem csatlakozó éllel; tehát H-ban a csúcs fokszáma vagy deg(w) − 1 (ami páros szám),  ha p nem alkot Hamilton-kört uv-n keresztül, vagy deg(w) − 2 (ami páratlan szám), ha p része egy uv-n keresztülmenő Hamilton-körnek. Mivel H páros számú páratlan csúccsal rendelkezik, G-nek páros számú uv-n keresztülmenő Hamilton-köre kell legyen.

Számítási bonyolultság
A cseregráf segítségével bizonyítani lehetett egyes kombinatorikai struktúrák létezését, felmerül azonban a kérdés, hogy milyen hatékonysággal találhatók meg ezek a struktúrák. Például, tegyük fel, hogy bemenetként megkapjuk egy 3-reguláris gráf Hamilton-körét; Smith tételéből következik, hogy léteznie kell egy második körnek is. Milyen gyorsan lehet ezt a kört megtalálni?
 vizsgálta az ilyen jellegű, számítási bonyolultságra vonatkozó kérdéseket, valamint általánosabban vizsgálta, hogy egy nagyméretű, impliciten megadott gráf egy páratlan csúcsát ismerve hogyan található meg egy második páratlan fokszámú csúcs. Meghatározta a PPA, illetve az irányított gráfokra vonatkozó PPAD bonyolultsági osztályokat az ilyen jellegű problémák lefedésére. Ezek fontos szerepet kapnak az algoritmikus játékelmélet területén, mivel a Nash-egyensúly kiszámítása ekvivalens a PPA osztály legnehezebb problémáinak kiszámításával.

Más alkalmazásai
A kézfogáslemmát felhasználják a Sperner-lemma és a hegymászóprobléma lineáris esetének bizonyításához is.

Fordítás

Jegyzetek

.
. Reprinted and translated in .
.
.

Gráfelméleti tételek
Lemmák
A matematika , azon belül a gráfelmélet területén a kézfogás-lemma vagy kézfogási lemma az az állítás , hogy minden véges irányítatlan gráf páros darab páratlan fokszámú csúccsal rendelkezik ( fokszám : a csúcsból kiinduló élek száma ) . Egy köznapi életből vett példával , ha egy partin néhány ember kezet fog egymással , a páratlan számú emberrel kezet rázók száma páros . A kézfogás-lemma a ( néha szintén kézfogás-lemmának hívott ) fokszámösszeg-képlet következménye , miszerint : ha a gráf csúcshalmazát V-vel , élhalmazát E-vel jelöljük . Mindkét eredményt igazolta a Königsbergi hidak problémáját vizsgáló híres elemzésében , ami a gráfelmélet megalapozásául szolgált . A páratlan fokszámú csúcsokat néha egyszerűen „ páratlan csúcs”-oknak nevezik ; ebben a terminológiában a kézfogáslemma úgy is megfogalmazható , hogy minden gráfnak páros számú páratlan csúcsa van . Bizonyítás Euler a fokszámösszeg-képletet a kettős leszámlálás nevű technikával bizonyítja : összeszámolja az érintkező ( v,e ) párosokat , ahol e egy él és a v csúcs az él valamely végpontja , két különböző módon . A v csúcs deg ( v ) párba tartozik bele , ahol deg ( v ) ( azaz v fokszáma ) a csúccsal érintkező élek száma . Tehát az érintkező párok száma a fokszámok összege . Azonban a gráf minden élevégpontja révén pontosan két érintkező párba tartozik , ezért az érintkező párok számaE| . Mivel a két képlet ugyanazt a halmazt számlálja meg , értéküknek azonosnak kell lennie . Egész számok összegzésekor az összeg párosságát nem befolyásolják a páros tagok ; a végösszeg akkor páros , ha páros darab páratlan tag van , és akkor páratlan , ha páratlan darab páratlan tag van . Mivel a fokszámösszeg-képlet egyik oldalán aE| páros szám található , bármely oldalon csak páros számú páratlan tag lehet ; ezért csak páros darab páratlan fokszámú csúcs létezhet . Egy másik bizonyítási módszer lehet a teljes indukció , megmutatva , hogy adott gráfból egy él eltávolításával nem juthatunk páratlan darab páratlan fokszámú csúcsot tartalmazó gráfhoz . Reguláris gráfok A fokszámösszeg-képletből következik , hogy bármely n csúcsú r-reguláris gráf nr/2 éllel rendelkezik . Ha pedig r páratlan szám , akkor az élek számának oszthatónak kell lennie r-rel . Végtelen gráfok A kézfogáslemma nem vonatkozik végtelen gráfokra , még akkor sem , ha csak véges számú páratlan fokszámú csúcsuk van . Például az ábrán látható végtelen útgráf egyetlen páratlan fokszámú csúccsal rendelkezik . Cseregráfok A tanulmányban listázott több kombinatorikai struktúráról megmutatható , hogy páros számosságú , egy megfelelő „ cseregráf” ( exchange graph ) páratlan fokszámú csúcsai segítségével . Például , ahogy azt Cedric Smith bizonyította , bármely Greguláris gráfban páros számú , a fix uv élen keresztülmenő Hamilton-körnek kell lennie ; a kézfogáslemma segítségével kiterjesztette a bizonyítást olyan gráfokra , ahol az összes csúcs fokszáma páratlan . A Thomason által definiált H cseregráf csúcsai kölcsönösen megfeleltethetők az eredeti gráf u-ban kezdődő és v-ben folytatódó Hamilton-útjainak . Két ilyen út , p1 és p2 akkor vannak H-ban éllel összekötve , ha p2 megkapható p1 végéhez egy él hozzáadásával és a közepéből egy másik eltávolításával ; ez szimmetrikus reláció , ezért H irányítatlan gráf . Ha a p út a w csúcsban végződik , akkor H-ban p-nek megfelelő csúcs fokszáma éppen a lehetőségek száma , ahogy p kiterjeszthető u-ba vissza nem csatlakozó éllel ; tehát H-ban a csúcs fokszáma vagy deg ( w ) − 1 ( ami páros szám ) , ha p nem alkot Hamilton-kört uv-n keresztül , vagy deg ( w ) − 2 ( ami páratlan szám ) , ha p része egy uv-n keresztülmenő Hamilton-körnek . Mivel H páros számú páratlan csúccsal rendelkezik , G-nek páros számú uv-n keresztülmenő Hamilton-köre kell legyen . Számítási bonyolultság A cseregráf segítségével bizonyítani lehetett egyes kombinatorikai struktúrák létezését , felmerül azonban a kérdés , hogy milyen hatékonysággal találhatók meg ezek a struktúrák . Például , tegyük fel , hogy bemenetként megkapjuk egyreguláris gráf Hamilton-körét ; Smith tételéből következik , hogy léteznie kell egy második körnek is . Milyen gyorsan lehet ezt a kört megtalálni ? vizsgálta az ilyen jellegű , számítási bonyolultságra vonatkozó kérdéseket , valamint általánosabban vizsgálta , hogy egy nagyméretű , impliciten megadott gráf egy páratlan csúcsát ismerve hogyan található meg egy második páratlan fokszámú csúcs . Meghatározta a PPA , illetve az irányított gráfokra vonatkozó PPAD bonyolultsági osztályokat az ilyen jellegű problémák lefedésére . Ezek fontos szerepet kapnak az algoritmikus játékelmélet területén , mivel a Nash-egyensúly kiszámítása ekvivalens a PPA osztály legnehezebb problémáinak kiszámításával . Más alkalmazásai A kézfogáslemmát felhasználják a Sperner-lemma és a hegymászóprobléma lineáris esetének bizonyításához is . Fordítás Jegyzetek . . Reprinted and translated in \ . . . Gráfelméleti tételek Lemmák