この用語はまだ監査を通っていません（未確認）。
握手補題
あくしゅほだい 1対1で対応handshaking lemma
名詞 別の言い方 handshake lemma
式と読み方
the sum over all vertices v of the degree of v equals two times the number of edges
定義
グラフのすべての頂点の次数の和は、辺の本数の 2 倍に等しいという定理。とくに、次数が奇数の頂点は偶数個ある。
The theorem that the degrees of all the vertices of a graph add up to twice the number of edges. In particular, every graph has an even number of vertices of odd degree.
例文
話し言葉 By the handshaking lemma, the degrees have to add up to an even number, so there's no graph with degrees 3, 3, and 3. 握手補題より次数の和は偶数になるはずだから、次数が 3, 3, 3 のグラフは存在しない。
書き言葉・答案 Use the handshaking lemma to show that every graph has an even number of vertices of odd degree. 握手補題を用いて、どのグラフでも次数が奇数の頂点は偶数個であることを示せ。
言い間違えやすいところ
- 名前はパーティーの握手のたとえから来ている。全員の握手の回数を足すと、1 回の握手を 2 人が 1 回ずつ数えるので、合計は必ず偶数になる。
- 1 本の辺は両端の 2 頂点の次数に 1 ずつ数えられる、というのが証明の中心。日本語では定理の名前を出さずに「次数の和は辺の数の 2 倍」と書くこともある。
- 用例コーパスでは書き言葉（すべて MIT の講義ノート）にわずかに出てくるだけで、話し言葉には出てこない。Levin の本では handshaking lemma ／ handshake lemma を合わせて 6 件（2.1 Problems and Definitions 5・1.5 Proofs about Discrete Structures 1）。