次数 (グラフ理論)
グラフ G = ( V , E ) {\displaystyle G=(V,E)} の次数の総和は次の公式で表される。
∑ v ∈ V deg  ( v ) = 2 | E | {\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}
これの証明は double counting という手法(二通りに数え上げる)の例である。グラフ内の辺と頂点の接合の個数は式の左辺のように各頂点の次数の総和でも表されるし、右辺のように辺の両端を数え上げてもよい。
この公式が意味するのは、次数が奇数の頂点の個数は偶数個だということである。これを握手補題 (handshaking lemma) と呼ぶ。この補題の名称は、あるグループ内で奇数人の人々と握手した人の数は常に偶数になるという数学の証明問題に由来する。