握手補題の証明
📂グラフ理論握手補題の証明
概要
任意のグラフにおいて、全ての頂点の次数の合計は偶数である。
説明
名前の「握手」とは見ての通り、各頂点が隣接する頂点と握手をした場合、その回数がちょうど次数の合計になるために付けられたものだ。
証明
グラフ G において、全ての次数の合計は正確に全てのエッジの数の2倍でなければならないから
v∈V(G)∑deg(v)=2∣E(G)∣
■
次数が奇数の頂点が奇数個存在すると仮定すると、全ての頂点の次数の合計は偶数になるが、これは握手レンマに反する。これにより、次の系を得る。
系
任意のグラフにおいて、次数が奇数の頂点は偶数個だけ存在しなければならない。