グラフと一筆書き(その 2) - Red cat の数学よもやま話

頂点の次数と握手補題

グラフ $G=(V,E,\varphi)$ の各頂点 $v\in V$ に対して、その次数を
$o(v)=2\sharp\{e\in E|\varphi(e)=[v,v]\}+\sharp\{e\in E|\exists w\in V(w\neq v\wedge\varphi(e)=[v,w]\}$
と定義します。要するに、v から伸びる辺の数なのですが、ループに関しては二重にカウントすることに注意してください。
$o(v)=0$ なる頂点を孤立点、 $o(v)=1$ なる頂点を端点と言います。
頂点の次数に関して、握手補題と言われる、次の命題が成り立ちます。

握手補題

$\sum_{v\in V}o(v)=2\sharp E$

この命題は直観的に明らかなので、証明はしません。この補題を使うと、次数が奇数である頂点は(0 個の場合も含めて)ちょうど偶数個だけあることが分かります。