📂グラフ理論

握手補題の証明

概要 ¹

任意のグラフにおいて、全ての頂点の次数の合計は偶数である。

説明

名前の「握手」とは見ての通り、各頂点が隣接する頂点と握手をした場合、その回数がちょうど次数の合計になるために付けられたものだ。

証明

グラフ $G$ において、全ての次数の合計は正確に全てのエッジの数の2倍でなければならないから $$ \sum_{v \in V(G)} \deg (v) = 2 \left| E(G) \right| $$

■

次数が奇数の頂点が奇数個存在すると仮定すると、全ての頂点の次数の合計は偶数になるが、これは握手レンマに反する。これにより、次の系を得る。

系

任意のグラフにおいて、次数が奇数の頂点は偶数個だけ存在しなければならない。