はじめに
基礎的な用語（サイクル、完全グラフなど）は既知であるものとして扱います。
弦グラフ
グラフに存在する任意の長さ以上の誘導サイクルが弦を持つ、つまり、サイクルを構成しないがサイクル内のある頂点を結ぶような辺が存在するとき、を弦グラフと呼ぶ。
弦グラフ
ところで、グラフ理論にはperfect elimination orderingという概念もあります（常に存在する訳ではないことに注意）。
perfect elimination ordering
グラフの頂点に対する順序がperfect elimination orderingであるとは、各頂点について、自身とに隣接かつより順序が後ろである頂点集合の誘導グラフが完全グラフであることを指す。
perfect elimination ordering
一見、両者は全く無関係なものに感じますが、実は次の定理が成り立ちます。
は弦グラフであるがperfect elimination orderingを持つ
今回はこの定理を証明していきます。
準備
の頂点において、を自身とに隣接する頂点集合とする。
がsimplicialであるとは、の誘導グラフが完全グラフであることを言う。
定義より、完全グラフ内の任意の頂点はsimplicialである。
が弦グラフならつ以上のsimplicialな頂点が存在する。さらにが完全グラフでないならば、はつの隣接しないsimplicialな頂点を持つ。
(i) のとき
頂点の間に辺があるならは完全グラフ、そうでないならは明らかにsimplicialである。
(ii) で補題が成り立つと仮定し、のとき
が完全グラフである場合は明らか。そうでないとき、隣接しない頂点を取ってくることができる。を分離する集合(つまり、の頂点集合から引くとが別の連結成分になるような集合)のうち、サイズが最小のものをとする。によって分離されたの連結成分をと表す。
もしが完全グラフでない場合、隣接していない頂点が存在し、の最小性からサイクルが存在する。しかし、このサイクルは長さ以上かつ弦がないので、が弦グラフであることに矛盾する。よって、は完全グラフ。
はの誘導グラフだから弦グラフであり、を満たす。よって、仮定よりは完全グラフまたは2つの隣接しないsimplicialな頂点を持つ。もしが完全グラフならばの頂点は全てsimplicialである。そうでないなら、つの隣接しないsimplicialな頂点が存在し、は完全グラフなのでどちらかはに入っている。つまり、についてsimplicialな頂点がの中につ以上存在する。対称性よりにも同様の議論ができるので、から一つずつsimplicialな頂点を取ってくると、両者は隣接していない。
定理1の証明
perfect elimination orderingを持つ弦グラフである
対偶を示す。が弦グラフでないなら、弦のないサイクルが存在する。頂点の順序でが最も前であったとすると、は異なる頂点であり隣接もしていない。よって、より順序が後ろの頂点集合は完全グラフにならないので、任意の順序はperfect elimination orderingとならない。
弦グラフであるperfect elimination orderingを持つ
が弦グラフだとすると、補題2よりsimplicialな頂点を取ることができる。このとき、定義からも弦グラフとなるから、の頂点がなくなるまでsimplicialな頂点を選んで並べれば、それはperfect elimination orderingとなる。
