主張

グラフの点の次数の総和は，辺の数の\(\,2\,\)倍になるという単純な補題ですね。

しかしこの簡単な補題は，グラフ理論のいたるところで出てくる重要なものです。

握手補題だけでも面白い応用がたくさん得られるので，気になる方はご覧ください。

よく使用される次の系も押さえておきましょう。

こちらの系の証明は簡単で，任意のグラフ\(\,G(V,E)\,\)について，
偶数次の点集合を\(\,V_e\,\)，奇数次の点集合を\(\,V_o\,\)とおくと，

\(\displaystyle \sum_{v\in V}\deg v =\sum_{v\in V_{e}}\deg v+\sum_{v\in V_{o}}\deg v\)

と分解できます。

よって握手補題\(\,\displaystyle \sum_{v\in V}\deg v =2|E|\,\)の式から

\(\displaystyle \sum_{v\in V_{o}}\deg v =\sum_{v\in V_{e}}\deg v-2|E|\)

となりますが，\(\,\displaystyle\sum_{v\in V_{e}}\deg v\,\)と\(\,2|E|\,\)は偶数なので，\(\displaystyle \sum_{v\in V_{o}}\deg v\,\)も偶数となります。

奇数の項を奇数個足し上げても奇数なので，
矛盾しないためには奇数次の点の個数\(\,|V_o|\,\)が偶数である必要が示されます。

したがって系は示されました。\(\quad\square\)

次節では名前の由来が分かる握手補題の証明について確認していきましょう。

証明

それでは握手補題の証明です。

\(2\,\)通りの方法で数える手法により示していきます。
この手法は握手補題以外にも用いられることが多いので，しっかり身に着けておきましょう。

点の次数の合計を次の\(\,2\,\)通りの方法で数えましょう。

\((1)\,\)単純に点の次数を数え上げる。

\((2)\,\)\(\,1\,\)つの辺がその\(\,2\,\)つの端点の次数に寄与していることに着目して数え上げる。

\((1)\,\)の数え方で数えるともちろん，\(\displaystyle \sum_{v\in V}\deg v\,\)となります。

\((2)\,\)の数え方で数えると，

辺\(\,1\,\)つにつき，\(\,2\,\)つの端点の次数に寄与しているので，\(\,2|E|\,\)となることが分かります。

したがって握手補題

\(\displaystyle \sum_{v\in V}\deg v =2|E|\)

は示されました。\(\quad\square\)

この証明は次のようなイメージで考えることもできます。

点から伸びている辺を「手」とみなし，グラフの辺はその手が「握手」することで作られると考えると

\(1\,\)つの握手のためには\(\,2\,\)つの手が必要であることから証明されているわけです。

このようなイメージで考えられるので，握手補題と呼ばれているわけですね。

今回の記事では詳しく言えば無向グラフの握手補題を示していますが，\(\,2\,\)通りの方法で数え上げる手法により，有効グラフの握手補題も簡単に証明できるので，証明をしっかり押さえておきましょう。

応用

単純な握手補題だけから理解できる面白い事実が下のようにたくさんあります。

【グラフ理論】ライツアウトとは？　遊び方から全ライトがONの状態は消灯できることの証明まで解説

握手補題からシュペルナーの補題を導く

握手補題と登山問題(mountain climbing problem)との関係

詳しい解説はこれから別の記事として書きたいと思うので，楽しみにしておいてください。

今回の記事では握手補題(handshaking lemma)を解説いたしました。

応用で紹介したことは，別の記事として書く予定なのでお待ちいただけると嬉しいです。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。