握手補題
#グラフ理論
多重グラフ$ Gに対して、次が成立する。
$ \sum_{v \in V(G)}d_G(v) = 2|E(G)|
有向グラフ$ Dに対するバリエーションは次のようになる
$ \sum_{v \in V(D)}od_G(v) = \sum_{v \in V(D)}id_G(v)
つまり、in-degreeの総和とout-degreeの総和とは等しい。
系
グラフの奇点の個数は偶数である
$ rが奇数の場合、r-正則グラフの位数は偶数である