握手補題と次数列
すべての頂点の次数の和は辺数の 2 倍。奇数次数の頂点は必ず偶数個。
頂点を 2 回クリックすると、その 2 頂点を結ぶ辺を追加（すでにあれば削除）します。何もない所をクリックすると選択解除。頂点をドラッグすると自由な位置へ移動できます。
Σ次数（次数の総和）
—
2E（辺数 ×2）
—
頂点数 V ／ 辺数 E
—
奇数次数の頂点数
—
—
偶数次数（0,2,4,…）
奇数次数（1,3,5,…）
選択中
次数列（降順）
握手補題（Handshaking lemma）。グラフの各頂点の次数（=その頂点から出ている辺の本数）をすべて足すと、必ず辺数 E の 2 倍になります。理由は単純で、1 本の辺は両端 2 つの頂点をそれぞれ数えるから、辺を 1 本引くと次数の総和はちょうど +2 されます。
その帰結として、奇数次数の頂点は必ず偶数個になります。総和 Σ次数 = 2E は偶数なので、奇数の足し算の個数が奇数だと合計が奇数になって矛盾するからです。頂点を 2 回クリックして辺を足したり消したりし、Σ次数 = 2E が常に成り立つこと、赤い頂点（奇数次数）が常に偶数個であることを確かめてみましょう。
その帰結として、奇数次数の頂点は必ず偶数個になります。総和 Σ次数 = 2E は偶数なので、奇数の足し算の個数が奇数だと合計が奇数になって矛盾するからです。頂点を 2 回クリックして辺を足したり消したりし、Σ次数 = 2E が常に成り立つこと、赤い頂点（奇数次数）が常に偶数個であることを確かめてみましょう。
いま何が起きている？
ここがポイント
- 1 本の辺は両端の次数を +1 ずつ ── だから次数の総和は辺を引くたび +2。よって
Σ deg(v) = 2E（握手補題）。総和は必ず偶数。 - 奇数次数の頂点は必ず偶数個 ── 偶数の Σ次数を作るには、奇数の項が偶数個そろっていないと辻褄が合わない。
- パーティの言い換え ── 会場で「奇数人と握手した人」の数は必ず偶数。誰がどう握手しても、これは絶対に崩れない。
- 次数列で分かること ── 次数の和が奇数になる数列（例 [1,1,1]）は、どんなグラフでも実現できない。