握手補題

グラフ理論において、握手補題とは、すべての有限無向グラフにおいて、奇数個の辺に接する頂点の数は偶数であるという主張である。例えば、握手する一団がいる場合、奇数人の他の人と握手する人の数は偶数である。 ^[1]握手補題は、次数和の公式（握手補題とも呼ばれる）の結果であり、^[2]それによれば、次数（各頂点が接する回数）の合計は、グラフの辺の数の2倍に等しい。両方の結果は、グラフ理論の研究の始まりとなった、レオンハルト・オイラー （1736年）の有名な論文「ケーニヒスベルクの七つの橋」で証明された。^[3]

ケーニヒスベルクの 7 つの橋問題 (後にオイラーツアーを形式化した) 以外にも、次数和公式の応用には、特定の組み合わせ構造の証明が含まれます。たとえば、スペルナーの補題や登山問題の証明では、公式の幾何学的特性が一般的に現れます。複雑性クラス PPA は、暗黙的に定義された大きなグラフに 1 つの奇数頂点がある場合に、2 番目の奇数頂点を見つけることの難しさを表します。

無向グラフは、頂点と、順序付けられていない頂点のペアを接続する辺のシステムで構成されます。どのグラフでも、頂点の次数は、 を端点とする辺の数として定義されます。頂点を自分自身に接続するループを含むことが許可されているグラフの場合、ハンドシェイク補題の目的で、ループは端点の次数に 2 単位寄与するものとしてカウントされます。^[2]次に、ハンドシェイク補題は、すべての有限グラフには、が奇数である頂点が偶数個存在する必要があると述べています。 ^[1]グラフ内の奇数次数の頂点は、奇数ノード(または奇数頂点) と呼ばれることがあります。^[4]この用語では、ハンドシェイク補題は、すべてのグラフには奇数ノードが偶数個あるというステートメントとして言い換えることができます。^{[4] [5]} ${\displaystyle \deg(v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle \deg(v)}$

次数和の公式は、 グラフ内のノード（または頂点）の集合で、 グラフ内の辺の集合であると述べています。つまり、頂点の次数の合計は辺の数の2倍に等しいです。^[6]有向グラフでは、次数和の公式の別の形式は、すべての頂点の入次数の合計と出次数の合計が両方とも辺の数に等しいと述べています。ここで、入次数は入ってくる辺の数であり、出次数は出ていく辺の数です。^[7]次数和の公式のバージョンは、有限集合族、または同等のマルチグラフにも適用されます。要素の次数の合計（次数はそれを含む集合の数に等しい）は、常に集合の濃度の合計に等しくなります。 ^[8]$${\displaystyle \sum _{v\in V}\deg v=2|E|,}$$${\displaystyle V}$${\displaystyle E}$

両方の結果は、与えられたグラフの任意の部分グラフ、特にその接続されたコンポーネントにも適用されます。結果として、任意の奇数頂点に対して、それを別の奇数頂点に接続するパスが存在する必要があります。^[9]

レオンハルト・オイラーは、ケーニヒスベルクの七つの橋に関する研究で、7つの橋をそれぞれ1回ずつ渡るケーニヒスベルク（現在のカリーニングラード）の街歩きツアーを求めるという握手補題を初めて証明した。これは、グラフ理論の用語で、市とその橋を表す連結グラフのオイラーパスまたはオイラーツアーを求めるものとして翻訳できる。つまり、各辺を1回ずつ横断するグラフのウォークであり、オイラーパスの場合は開始点とは別の頂点で終了し、オイラーツアーの場合は開始点に戻る。オイラーはこの問題の基本的な結果をグラフ内の奇数頂点の数で述べたが、握手補題ではその数が偶数に制限される。この数が0の場合、オイラーツアーが存在し、2の場合、オイラーパスが存在する。そうでない場合、問題は解くことができない。ケーニヒスベルクの7つの橋の場合、問題を表すグラフには4つの奇数の頂点があり、オイラー経路もオイラー巡回も存在しません。^[3]そのため、ケーニヒスベルクの7つの橋すべてを、同じ橋を繰り返さずに巡回することは不可能でした。

巡回セールスマン問題を近似するクリストフィード・セルジュコフアルゴリズムでは、次数和公式の幾何学的意味が重要な役割を果たしており、アルゴリズムが頂点をペアで接続して、オイラーツアーが近似TSPツアーを形成するグラフを構築できるようにしています。^[10]

いくつかの組み合わせ構造は、適切な「交換グラフ」の奇数頂点に関連付けることで、偶数であることが示されます。^[11]

たとえば、CAB スミスが証明したように、任意の立方体グラフ には、任意の固定辺 を通る偶数個のハミルトン閉路が存在する必要があります。これらは、各頂点を正確に 1 回通過する閉路です。トーマスン (1978) は、握手補題に基づく証明を使用して、この結果をすべての頂点の次数が奇数であるグラフに拡張しました。トーマスンは、頂点が、辺 から始まり辺 まで続くのハミルトン経路と 1 対 1 で対応している交換グラフ を定義します。このような 2 つの経路と は、の終端に新しい辺を追加し、 の中央から別の辺を削除することで を得られる場合、 の辺で接続されていると定義されます。この操作は可逆で、対称関係を形成します。無向グラフも同様です。経路が頂点 で終了する場合、の に対応する頂点の次数は、 に接続しない辺によって延長できる方法の数に等しくなります。つまり、が を通るハミルトン閉路の一部を形成しない場合は におけるこの頂点の次数は(偶数)であり、が を通るハミルトン閉路の一部である場合は におけるこの頂点の次数は (奇数)である。には奇頂点が偶数個あるため、には を通るハミルトン閉路が偶数個なければならない。^[12]${\displaystyle G}$${\displaystyle uv}$${\displaystyle H}$${\displaystyle G}$${\displaystyle u}$${\displaystyle uv}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle H}$${\displaystyle p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{1}}$${\displaystyle H}$${\displaystyle p}$${\displaystyle w}$${\displaystyle p}$${\displaystyle H}$${\displaystyle p}$${\displaystyle u}$${\displaystyle H}$${\displaystyle \deg(w)-1}$${\displaystyle p}$${\displaystyle uv}$${\displaystyle \deg(w)-2}$${\displaystyle p}$${\displaystyle uv}$${\displaystyle H}$${\displaystyle G}$${\displaystyle uv}$

ハンドシェイク補題（または次数和の公式）は、数学における他のいくつかの結果の証明にも使用されます。これには次のものが含まれます。

• スペルナーの補題は、大きな三角形を辺同士が接する小さな三角形に分割し、頂点に3色をつけて、大きな三角形の各辺に2色だけを使うようにすると、小さな三角形の少なくとも1つには3色すべての頂点がある、というものである。この補題は、不動点定理、根探索アルゴリズム、公平な分割に応用されている。この補題の証明の1つは、三角形（小さい三角形と大きい三角形の両方）を頂点とし、辺が特定の2色の頂点を共有する三角形のペアを繋ぐ交換グラフを形成する。この交換グラフでは、大きな三角形は必然的に奇数の次数を持ち、3色すべてを持つ小さな三角形も奇数次になるが、他の小さな三角形はそうではない。握手補題により、3色すべてを持つ小さな三角形は奇数個あるはずなので、そのような三角形が少なくとも1つは存在しなければならない。^[13]

• 山登り問題とは、単位区間上の十分によく機能する関数で、区間の両端で値が等しいものについて、区間の両端から出発して 2 点の運動を調整し、運動中ずっと値が等しい点にとどまりながら中間のどこかで出会うようにすることが可能であるというものである。この証明の 1 つは、関数を同じ端点を持つ区分線形関数で近似し、移動する 2 点の位置を単位正方形内の 1 点の座標でパラメータ化し、2 点の利用可能な位置がこの正方形に埋め込まれた有限グラフを形成し、開始位置とその反転のみが奇数頂点となることを示すことである。握手補題により、これら 2 つの位置はグラフの同じ連結成分に属し、一方から他方へのパスは必ず目的の会合点を通過する。^[14]
• 再構築予想は、グラフから1つの頂点を削除して形成されたサブグラフの多重集合からグラフの構造を一意に決定する問題に関する。この情報が与えられれば、次数和の公式を使用して、与えられたグラフの辺の数と各頂点の次数を復元することができる。これにより、与えられたグラフが正則グラフであるかどうかを決定でき、そうであれば、次数が低すぎるサブグラフの頂点すべてに新しい近傍を追加することで、頂点を削除したサブグラフから一意に決定できる。したがって、すべての正則グラフを再構築できる。^[15]
• ヘックスゲームは2人のプレイヤーがプレイする。2人は平行四辺形の盤を六角形で敷き詰め、自分の色の駒を置き、片方のプレイヤーが盤の片側からもう片側まで隣接する駒がつながった道を作るまで続ける。このゲームは引き分けにはならない。盤が駒で完全に埋まる頃には、どちらかのプレイヤーが勝ちの道を作っている。このことの証明の1つは、埋め尽くされたゲーム盤からグラフを作ることだ。グラフの頂点は六角形の角にあり、辺は2人のプレイヤーの色を分ける六角形の辺にある。このグラフは盤の角に4つの奇数頂点を持ち、他の部分には偶数頂点を持つ。そのため、2つの角を結ぶ道が必ず含まれ、その道の片側には必ずどちらかのプレイヤーの勝ちの道が存在する。^[16]

オイラーの次数和公式の証明では、 を二重に数える手法が使われている。つまり、が辺で頂点がその端点の 1 つである場合の接続対の数を 2 つの異なる方法で数える。頂点は対に属し、( の次数) はそれに接続する辺の数である。したがって、接続対の数は次数の合計である。しかし、グラフの各辺は、その端点ごとに 1 つずつ、正確に 2 つの接続対に属しているため、接続対の数は である。これら 2 つの公式は同じオブジェクトのセットを数えるため、それらは等しい値を持つ必要がある。同じ証明は、グラフの接続行列のエントリを2 つの方法で合計すること、つまり行ごとに次数の合計を取得し、列ごとに辺の数を 2 倍にすることとして解釈できる。^[5]${\displaystyle (v,e)}$${\displaystyle e}$${\displaystyle v}$${\displaystyle v}$${\displaystyle \deg(v)}$${\displaystyle \deg(v)}$${\displaystyle v}$${\displaystyle 2|E|}$

グラフの場合、握手補題は次数和公式の系として成り立つ。^[8]整数の和では、和の偶奇性は和の偶数項の影響を受けない。つまり、奇数項が偶数個ある場合は全体の和は偶数であり、奇数項が奇数個ある場合は奇数である。次数和公式の片辺は偶数であるため、もう一方の辺の和には奇数項が偶数個含まれている必要がある。つまり、奇数次数の頂点が偶数個含まれている必要がある。^[5]${\displaystyle 2|E|}$

あるいは、数学的帰納法を使って次数和の公式を証明することも可能である^[2]。あるいは、与えられたグラフから一度に1つの辺を削除し、その端点の次数に関するケース分析を使用して、この削除が奇数次頂点の数の偶数性に与える影響を判断することによって、奇数次頂点の数が偶数であることを直接証明することもできる^{[17] 。}

次数和の公式は、頂点を持つすべての-正則グラフには辺があることを意味している。^[18]辺の数は整数でなければならないため、 が奇数のときは頂点の数は偶数でなければならない。^[19]さらに、 が奇数のときは、辺の数は で割り切れなければならない。^[20]${\displaystyle r}$${\displaystyle n}$${\displaystyle nr/2}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$

二部グラフでは、頂点が 2 つのサブセットに分割され、各辺は各サブセットに 1 つのエンドポイントを持ちます。同じ二重カウントの議論から、各サブセットでは、次数の合計がグラフの辺の数に等しくなります。特に、両方のサブセットの次数の合計は等しくなります。^[21]双正則グラフでは、頂点がサブセットに分割され、サブセット内のすべての頂点が次数 である場合、 が必ず成り立ち、両方とも辺の数に等しくなります。^[22]${\displaystyle V_{1}}$${\displaystyle V_{2}}$${\displaystyle V_{i}}$${\displaystyle r_{i}}$${\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}$

ハンドシェイク補題は、通常の形式では、たとえそれが有限個の奇数次頂点しか持たない場合でも、無限グラフには適用されません。たとえば、1 つの端点を持つ無限パス グラフには、偶数個の奇数次頂点ではなく、1 つの奇数次頂点しかありません。ただし、端の概念を使用して、ハンドシェイク補題のバージョンを定式化することは可能です。端とは、半無限パス (「光線」) の同値類であり、2 つの光線が、それぞれの光線から無限に多くの頂点を使用する 3 番目の光線が存在する場合に、それらの光線を同等と見なします。端の次数は、端に含まれる辺が互いに素な光線の最大数であり、端の次数が有限かつ奇数である場合、端は奇数です。より一般的には、すべての頂点の次数が有限であるグラフでは、端が無限次であるかどうかに関係なく、端を奇数または偶数として定義できます。そして、そのようなグラフでは、奇数の頂点と奇数の端の数を合計すると、偶数か無限大になります。^[23]

ガライの定理により、任意のグラフの頂点は のように分割できる。ここで、結果として得られる 2つの誘導部分グラフでは、はすべての次数が偶数で、 はすべての次数が奇数である。ここで、握手補題により は偶数でなければならない。また、多数の頂点を持つ偶数次および奇数次の誘導部分グラフを見つけることも可能である。偶数次の誘導部分グラフは、少なくとも半分の頂点で見つけることができ、奇数次の誘導部分グラフ (孤立した頂点のないグラフ) は で見つけることができる。^{[24] [25]}${\displaystyle V=V_{e}\cup V_{o}}$${\displaystyle G[V_{e}]}$${\displaystyle G[V_{o}]}$${\displaystyle |V_{o}|}$${\displaystyle |V_{o}|/|V|>1/10000}$

組み合わせ構造の存在を証明するための交換グラフ法に関連して、これらの構造をどれだけ効率的に見つけることができるかという問いは興味深い。例えば、入力として立方体グラフのハミルトン閉路が与えられたとしよう。スミスの定理から、2 番目の閉路が存在することがわかる。この 2 番目の閉路はどれだけ速く見つけることができるだろうか。パパディミトリウ (1994) は、このような問題、あるいはもっと一般的には、暗黙的に定義された大きなグラフで単一の奇数頂点が与えられたときに 2 番目の奇数次頂点を見つける問題の計算複雑性について調査した。彼は、このような問題をカプセル化するために複雑性クラスPPA を定義した。 ^[26]有向グラフで定義された密接に関連するクラスPPAD は、ナッシュ均衡を計算することがこのクラスで最も難しい問題と計算的に同等であるため、アルゴリズムゲーム理論で大きな注目を集めている。^[27]

計算量クラスPPAに対して完全であることが証明された計算問題には、スペルナーの補題^[28]やホビー・ライス定理[ ^29]に従った資源の公平な分割に関連する計算タスクが含まれる。