📂グラフ理論

グラフ理論におけるディラックの定理の証明

定理 ¹

$G$が頂点が$n ( \ge 3)$個の単純グラフだとする。

• [1] ディラックの定理：$G$のすべての頂点$v$に対して$\deg (v) \ge n / 2$が成り立てば、$G$はハミルトングラフである。
• [2] オレの定理：$G$ の互いに隣接しない任意の2頂点のペア$(v ,w)$について、$\deg (v) + \deg(w) \ge n$が成り立てば、$G$はハミルトングラフである。

説明

ディラックの定理は、グラフがハミルトングラフであるための十分条件を同定するもので、必ずしも同等ではないが、1952年に証明された後、1960年にオレ^oreによって一般化された。しかし、ディラックの定理はその地位を保ち、オレの定理はその推論定理として残ることになった。

証明

戦略：オレの定理がディラックの定理を含意することは明らかなので、オレの定理の証明だけで十分である。背理法で、$G$に$m$個のエッジを加えてもハミルトングラフであることを示し、数学的帰納法を通じて、エッジを$m , m -1 , \cdots , 1 , 0$個だけさらに加えてもハミルトングラフになることを示すことで、結局$G$がハミルトングラフであるという結論を導き出す。

[2]

$\deg (v) + \deg(w) \ge n$ であるが、$G$がハミルトングラフでないと仮定してみる。 $$ v_{1} \to \cdots \to v_{n} $$ $n$個の頂点$v_{1} , \cdots , v_{n} \in V(G)$に対して、いくつかのエッジを加えたグラフ$H$では上記のようにすべての頂点を通るパスを作ることができるだろう。ただし、$v_{1}$と$v_{n}$を繋ぐエッジだけがなくてサイクルではなく、$H$もハミルトングラフではないとする。もちろん、$H$にエッジを追加して次数が増えただけで、元の$G$で満たされていた $$\deg (v) + \deg(w) \ge n$$ に反するわけではない。また、$v_{1}$と$v_{n}$は隣接していないため、 $$\deg (v_{1}) + \deg(v_{n}) \ge n$$ である。$v_{1}$と$v_{n}$の次数の合計が頂点の総数より多いということは、$v_{1}$と$v_{i}$が隣接していて、$v_{n}$と$v_{i-1}$が隣接するような自然数 $2 \le i \le n$が存在するということである。それなら、次のようなサイクルが存在するべきである。 $$ v_{1} \to v_{2} \to \cdots \to v_{i-1} \to v_{n} \to v_{n-1} \to \cdots \to v_{i+1} \to v_{i} \to v_{1} $$ これは、$H$がハミルトングラフではないという主張に矛盾する。この議論は、$G$に追加されたが$H$のハミルトンサイクルに含まれるエッジをひとつ除去して新しいグラフ$h '$を作る場合にも同様に適用され、結局$G$がハミルトングラフではないという仮定に矛盾する。

■