Skip to content

握手の補題

概要

グラフ \(G=(V,E)\) の頂点 \(v\) の次数を \(d_v\) とおくとき以下が成り立つ。

\[ \sum_{v\in V}d_v=2|E| \]

握手の補題から以下のことも成り立つ。

  1. グラフの次数の総和は偶数となる
  2. 次数が奇数であるような頂点の個数は偶数個

証明

全ての辺 (edge) には端点となる頂点が必ず 2 つ存在する。したがって 1 つの辺に付き次数が 2 回カウントされることとなり、握手の補題の主張が成り立つことがわかる。

発展

グラフの次数に関する他の条件

大雑把には「グラフの次数は偏りすぎにはならない」

グラフの次数を降順に \(d_1,d_2,...,d_n\) とおくとき、任意の \(k\) に対して以下の式が成り立つ。

\[ \sum_{i=1}^{k}d_i \geq k(k-1)+\sum_{i=k+1}^{n}\textrm{min}(d_i,k)\hspace{10mm}(k=1,2,...,n) \]

頂点 1 から頂点 \(k\) までを一つのグループとして考える。

  • 左辺: グループの頂点の次数の和
  • 右辺第 1 項: グループ内の辺の本数の最大値は \(\frac{k(k-1)}{2}\) 本 = グループで消費する次数は \(k(k-1)\)
  • 右辺第 2 項: グループ内の頂点とグループ外の頂点 \(i\) を結ぶことで消費できる次数の数は \(d_i\) と \(k\) の内小さいほうとなる。

エルデシュガライの定理

降順に並べた次数列 \(d_1,d_2,...,d_n\) を実現する単純グラフが存在する必要十分条件は以下の 2 つの条件を満たすことになる。

  1. \(\sum_{v \in V}d_v\) が偶数
  2. \(\sum_{i=1}^{k}d_i \geq k(k-1)+\sum_{i=k+1}^{n}\textrm{min}(d_i,k)\hspace{10mm}(k=1,2,...,n)\)

参考