握手補題

内容

任意の有限グラフ $G=(V,E)$ において、$\sum_{v \in V} \deg(v) = 2|E|$ が成り立つ。したがって、次数が奇数である頂点の個数は偶数である。

なぜ正しいのか?

どの辺もちょうど二つの端点を持つので、すべての頂点の次数を足し合わせると、各辺はちょうど二回数えられる——パーティーでの握手が、両方の参加者からそれぞれ一回ずつ数えられるのと同じである。合計はある整数の二倍なので偶数となり、これにより奇数次数の頂点の個数も偶数でなければならないことになる。

この定理を使うトピック

関連する定理

ステップごとの証明

この定理のステップごとの証明はまだありません。