📂グラフ理論

エルデシュ＝ガライの定理

ビルドアップ

1. グラフ $G$ の次数を重複を含めて集めた集合をグラフスコアと言い、$G$ のグラフスコアを降順に並べたシーケンスを$G$のディグリーシーケンスと言う。
2. 減少しない自然数のシーケンス $D = (d_{1} , \cdots , d_{n})$ にたいして、$n$ 個のバーテックス $v_{1} , \cdots , v_{n}$ が次の条件を満たせば、$G$ が存在するなら $D$ はグラフィックであると言い、そのグラフ $G$ を$D$ の実現と呼ぶ。

例えば、上記のようなグラフ $G_{0}$ が与えられた場合、グラフスコアは次のようになる。 $$\left\{ 1,5,3,5,2,1,5,2 \right\}$$ そして、降順（減少しない）に並べたディグリーシーケンスは次の通りである。 $$D_{0} = (5,5,5,3,2,2,1,1)$$

数学者なら誰でも、ディグリーシーケンスだけを持ってグラフを作り出せるかどうかに関心を持つだろう。それが可能であれば、そのシーケンスがグラフを生み出すことができるという意味であり、グラフィックであるとかグラフ化可能であるという概念を考え出せるだろう。上の例から続けると、$G_{0}$ は$D_{0}$ の実現の一つと見ることができる。[ 注: 実現は一意に存在する必要はない。 ]

このように、シーケンスがグラフィックであるかに関する同値条件は、次の定理で明らかにされている。

定理

エルデシュ–ガライの定理

シーケンス $(d_{1} , \cdots , d_{n})$ がグラフィックであることは、次の2つの条件を同時に満たすことと同値である。 $$\sum_{i=1}^{n} d_{i} \in 2 \mathbb{Z} \\ \sum_{i=1}^{k} d_{i} \le k ( k-1) + \sum_{i=k+1}^{n} \min (k, d_{i}) , \qquad 1 \le k \le n$$

---

• $2 \mathbb{Z}$ は偶数集合を意味する。

証明 ¹

省略する。

参照

しかし、これは実現の存在を保証するだけで、その実現が具体的にどのようなものかは示さないため、ハベル–ハキミ アルゴリズムのような方法で直接見つける必要がある。これは、オイラーグラフで具体的なオイラートレイルを見つける場合にフルーリー アルゴリズムを使う必要があるのと似ている。