§２．握 手 定 理
| 今、あるホテルの松の間、竹の間、梅の間等いくつかの会場でパ−ティ−が行われています。それぞれの会場では出席者が楽しそうに歓談をし、握手が交わされています。パ−ティ−終了後、松の間の出席者全員に、パ−ティ−の最中、何人と握手を交わしたかというアンケ−トをとりました。 同様に、竹の間、梅の間等、すべての会場でもアンケ−トを行いました。 アンケ−トを集計したところ、ある面白い結果が得られました。というのは、各会場とも、１人、３人、５人、……というように、奇数人と握手をした人が、偶数人いたということです。 これは、偶然、このような結果になったのでしょうか。それとも、奇数人と握手をした人の人数が、必ず偶数になるといえるのでしょうか。 |
図１０ |
これを調べるために、グラフを利用してみることにしましょう。
例えば、松の間の出席者が15人であったとし、15人それぞれをv1,v2,…,v15で表わし、握手したもの同士を線で結んで完成したものを図10のグラフとします。
グラフでは、各人の握手回数はその人を表わす点に接続している線の本数（次数）に等しくなります。
例えば、v3の握手回数は
d(v3)＝５
すなわち、５回であることは図10を見ればわかります。
ここで、上の問題をグラフ理論の用語を使って言い換えると、
| どのようなグラフにおいても、奇点の数は必ず偶数個存在するのか？ |
となります。
そこで、図10のグラフを例に、各点の次数の和とグラフの線の数に注目してみましょう。
 |
d(v1)+d(v2)+d(v3)+d(v4)+d(v5)+d(v6)+d(v7)+d(v8)+d(v9)+d(v10)+d(v11)+d(v12)+d(v13)+d(v14)+d(v15)＝(線の本数)×２
となることが分かります。例えば、d(v3)を求めるとき、点v3に接続している線の数を数えますが、数えた線に印を入れていくことにします。するとd(v1)からd(v15)まで数え終えたとき、グラフの全ての線に２つずつ印が入っていることに気付くことでしょう。したがって、各点の次数の和が(線の本数)×２に等しくなるのです。ここで、各点の次数の和が偶数になるという事実に注目してください。各点は奇点か偶点のいずれかであり、偶点の次数和が偶数になることは明らかであるから、各点の次数和が偶数になるためには、奇点の数が偶数個でなければならないのです。したがって、次の定理が成り立ちます。
| 定理２．１（握手定理） どのようなグラフにおいても、奇点は必ず偶数個存在する。 |