User:Z423x5c6/握手引理

喺幅圖入面，有偶數個（2、4、5、6四個）頂點嘅度係奇數，六粒點嘅度和係 2 + 3 + 2 + 3 + 3 + 1 = 14，係邊數（7）嘅兩倍。

圖論入面，握手引理（英文：handshaking lemma）指出，喺一個有限無向圖入面，連住「單數咁多條邊」嘅頂點數量係雙數。用日常嘅語言嘅話，喺一個聚會入面啲人互相握手，同過單數咁多個人握手嘅人數一定係雙數。握手引理可以用度和公式嚟證明，而有啲人直程會將度和公式叫做握手引理。度和公式指出，一幅圖所有點嘅度加埋等於邊嘅數量嘅兩倍。兩個定理都係由歐拉喺佢好出名、研究七橋問題嘅論文入面證明，呢篇亦都係世界上第一篇研究圖論嘅論文。

除咗用嚟研究七橋問題同佢嘅推廣一筆畫問題之外，握手引理可以證明某啲組合性嘅結構數量一定係雙數，亦都可以用嚟幫手證明Sperner引理同行山問題。畀一幅好大嘅隱定義圖同埋入面一粒奇度嘅點，要搵另一粒奇度點出嚟嘅運算複雜度叫做PPA類。

定義同定理內容

一個無向圖入面有一柞點，另外有一柞邊，每條邊連住兩點，呢啲邊係無方向嘅，即係話A點連去B點同B點連去A點無分別。圖入面，一粒頂點v嘅度（degree）即係有幾多條邊連去呢一點。如果幅圖容許有迴圈（即係一點連去佢自己度），咁計度嗰陣呢啲邊計兩條。用呢啲術語嘅話，握手引理就係講一幅有限圖入邊，度係奇數嘅點數量係一個雙數。「度係奇數嘅點」有時又叫奇點（odd node/odd vertex），咁嘅話握手引理即係話任何有限圖都有偶數粒奇點。

度和公式指出，

$\sum _{v\in V}\deg v=2|E|$，

其中$V$係幅圖嘅點集，$E$係幅圖嘅邊集，亦即係話所有點嘅度加埋係等於邊數嘅兩倍。度和公式亦都有有向圖嘅版本，指出一幅圖嘅入度和同出度和都等於邊數，呢到入度係數入一粒點嘅邊，出度就數出一粒點嘅邊。度和定理仲有一個集合族嘅版本，集合族等價於超圖，點嘅度和等於啲集合基數嘅和。

握手引理同度和公式都可以應用落去子圖到，包括幅圖嘅連通部分，其中一個推論就係，畀一粒奇點，一定存在一條路徑將佢連去另一粒奇點。

應用

一筆畫

歐拉喺佢篇研究七橋問題嘅論文入面首次證明握手引理。七橋問題係問可唔可以喺柯尼斯堡（依家嘅加里寧格勒）入面行一個圈，而且嗰七條橋都係啱啱好經過一次。呢篇文開創咗圖論同埋拓樸學。用現代嘅圖論語言嚟講，條問題即係問喺右邊嘅圖入面，存唔存在歐拉路徑或者歐拉迴路。歐拉解決咗呢個問題，個答案同圖入面嘅奇點數量有關。握手引理指出呢個奇點數量一定係偶數，若果係 0 嘅話幅圖就有歐拉迴路，係 2 嘅話就有歐拉路徑（不過唔係歐拉迴路，即係起點同終點係唔同嘅），4 或以上就歐拉迴路同歐拉路徑都無。

用 Christofides–Serdyukov 算法嚟逼近旅行推銷員問題（traveling salesperson problem，TSP）嘅時候，握手引理好重要，因為佢令個算法可以將啲點連成一對對，用歐拉迴路嚟逼近 TSP 迴路。

柯尼斯堡七條橋嘅佈局

對應嘅圖，點代表一笪地，邊代表一條橋

特別嘅圖

Clebsch 圖係一幅5-正則圖，頂點數量係雙數 (16)，邊數係 5 嘅倍數 (40)。

菱形十二面體係雙正則圖，有 6 粒 4度點，8 粒 3度點，6 × 4 = 8 × 3 = 24，而 24 正正係邊數。

正則圖

度和公式指出，一幅有 $n$ 粒點嘅 $r$-正則圖會有 ${\frac {nr}{2}}$ 條邊，而由於邊嘅數量一定係整數，若果 $r$ 係單數嘅話頂點嘅數量就一定要係雙數，而且喺呢個時候邊數一定可以被 $r$ 整除。

無限圖

得一粒奇點嘅無限圖