駆け足で学ぶ「グラフマイナー定理」

0. 概要

グラフマイナー定理とは

有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered)

という定理です.

...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つであるグラフマイナー定理について、その中身と研究背景をグラフ理論の観点から可能な限りちゃんと書いていきたいと思います. なお本記事では「グラフ」とは単に有限グラフのことを指すこととします. また, 頂点にラベルは付いていないものとします.

　章の構成は以下です. グラフマイナー定理の凄さをアピールする記事なので, 研究背景の説明に重きをおいています. 内容を知りたい方は4章から読んでください.

•  1~3章 : グラフマイナー定理の研究背景
• 4章 : グラフマイナー定理の内容の説明
• 5章 : 木に関するグラフマイナー定理

1. 平面グラフのマイナーによる特徴づけ

　グラフマイナー定理について説明する前にその研究動機について説明したいと思います.

　世の中には様々なグラフがありますが, その中でも平面グラフと呼ばれる種類のグラフがあり, これまで多くの研究がなされてきました. 平面グラフとはグラフを紙面上に辺を交差せずに描けるようなグラフのことを指します. 数学的には球への埋め込みを使って定義されます.

図1: 左のグラフは一見すると中央で辺が交差しているように見えますが,
右のように描くことにより交差せずに描けるので, このグラフは平面グラフです.

図2: 左のグラフは $K_5$, 右のグラフは $K_{3,3}$.
どちらのグラフも平面グラフではない.

　図1のグラフはどちらも「4つの頂点を持ち, どの頂点ペアも辺で結ばれているようなグラフ」です. このグラフを頂点数4の完全グラフと呼び, $K_4$と表記します. $K_4$は図1右のように描けば辺を交差させずに平面上に描くことが出来ます.
　一方で $K_5$ (図2左) はどうかというと, 実はどんなに頑張っても決して辺を交差させずに平面上に描くことは出来ません. また, 図2右のグラフは「上と下に三つずつ頂点をもち, 上の頂点と下の頂点のペアはどれも辺で結ばれている」グラフです. このグラフは上下に三つずつ頂点があるので $K_{3,3}$と表記します (完全二部グラフとも呼ばれます) このグラフも実は平面グラフでないことを証明することが出来ます. 証明は例えば高校数学の美しい物語に載っています.

　さて, 与えられたグラフが平面的であるかどうか をどうやって判定すれば良いでしょうか. 実はこの問題はグラフの頂点数 $n$ に対して $O(n)$時間で解くことが出来ます [1].

　そのアルゴリズムで使われている定理が Kuratowski の定理 です. この定理は平面グラフの特徴づけを与えている定理で, 次のようなものです:

定理 (Kuratowski, 1930)

グラフ$G$が平面グラフであることの必要十分条件は, $G$が$K_5$と$K_{3,3}$の細分を部分グラフとして含まないことである.

ここでグラフ$H$の細分とは, $H$の辺をいくつか指定して, それぞれの辺を任意の長さ(ただし1以上)のパスに置き換えて得られるグラフです. 具体的には次の図を見てください.

図3: $K_4$の細分の例です.
(上):太線で書かれた辺を長さ3のパスに置き換えています.
(下):選択する辺は複数本でもよく, 更にそれぞれ異なる長さのパスに置換しても良いです.

　グラフ$G$がグラフ$H$を部分グラフとして含む, というのは $E(G),\,E(H)$ をそれぞれ $G,\,H$ の辺集合としたときに, $E(H) \subseteq E(G)$ となることを言います. $G$から頂点と辺を何本か取り除くと $H$ が得られる, と言い換えることも出来ます.

　$K_5$の細分と$K_{3,3}$の細分を部分グラフとして含まない, というのは中々強い要請であることが分かります. 例えば, これらの細分を含むようなグラフは必ず次数3以上の頂点を4つ以上持つため, 「次数3以上の頂点が高々3つならば, そのグラフは平面グラフである」ということが証明できたりするわけです(*).

(*): グラフ $G$ が グラフ $H$ の細分を部分グラフとして含むとき, $G$ は $H$ を 位相的マイナーとして含む, と言うこともあります.

　また, Kuratowski の定理と似たような平面グラフの特徴づけの定理が次に示す Wagner の定理です.

定理 (Wagner, 1937)

グラフ$G$が平面グラフであることの必要十分条件は, $G$が$K_5$と$K_{3,3}$をマイナーとして含まないことである.



Kuratowski の定理と似ていますがこちらには「マイナー」という単語が出てきています.

グラフ $G$ がグラフ $H$ をマイナーとして含む, というのは, $G$ の適当な部分グラフ $F$ が存在して, $H$は$F$の有限回の縮約操作によって得られる, という意味です (図4).

図4: $G$ のある部分グラフ $F$ から縮約操作によって $H$ が得られている.
このとき $G$ は $H$ をマイナーとして含むという.

　縮約操作とは, 辺を一つ指定してその両端点にある頂点の一つの頂点に合体させる操作を指します. 自己ループや多重辺の生じうるものとします. 次の図を見てください.

図5: 右のグラフが縮約後のグラフになります.

　すなわち, $G$ から頂点と辺を幾つか除いた後に辺の縮約を行うことによって $H$ が得られたとき, $G$ は $H$ をマイナーとして含む, ということになります.

　さて, Wagner の定理により, $G$が平面グラフであることの必要十分条件とは, $G$の適当な部分グラフ$H$が存在して, $H$に適当な縮約操作を繰り返してやると $K_5$ または $K_{3,3}$ が得られる, ということになります. このように 「グラフ $X$ をマイナーとして含まない」ようなグラフの族 $\mathcal{G}$ に対して $X$ を $\mathcal{G}$ の禁止マイナーと呼ぶこともあります. 今回で言えば, $K_5$ と $K_{3,3}$ は平面グラフの禁止マイナーということになります.

2. 四色定理　～Wagnerのアプローチ, Hadwiger 予想～

　この章は少し蛇足気味です. 飛ばして読んでもかまいません. 当時のグラフ理論界では「四色問題」が大ブームでした. 四色問題とは次のような問題です:

四色問題 

平面グラフは4-彩色可能である.


　彩色とは, グラフの頂点に色を塗ることですが, 条件として隣接する頂点同士は異なる色で塗らなければなりません. グラフ $G$ が $k$ 色で彩色できる場合は, $G$ は $k$-彩色可能である と言ったりします. $k$ 色で彩色可能ならば $k+1$ 色で彩色することも明らかに可能なので, グラフ $G$ を彩色するのに必要な色の種類数を定義することができます. この値を 彩色数 と呼び, $\xi(G)$ と表します.

　Wagner は 平面グラフのマイナーによる特徴付けというアプローチから四色問題に取り組んでいました. 結論から言うと失敗するのですが, このときに「$K_5$ をマイナーとして含まないグラフはどのようなグラフか」という問題に対して Wagner の分解定理 と呼ばれる有名な定理を示しています.

　例えば, $K_2$ をマイナーとして含まないグラフというのは 「辺を含まないグラフ」であり, $K_3$ をマイナーとして含まないグラフというのは, 森 (閉路を含まないグラフ) となります.

　ここで重要なのは, これまでの結果として

• $K_2$をマイナーとして含まないグラフは 1-彩色可能
• $K_3$をマイナーとして含まないグラフは 2-彩色可能
• $K_4$をマイナーとして含まないグラフは 3-彩色可能
• $K_5$をマイナーとして含まないグラフは 4-彩色可能

　ということが示されたことです. では,

$K_{t+1}$ をマイナーとして含まないグラフは $t$-彩色可能 なのでしょうか？

この予想は Hadwiger 予想と呼ばれるもので, グラフ理論の最重要かつ最難な未解決問題といわれています. (今なお未解決です)

3. Wagner 予想

　2.で述べたように, Wagner は 四色問題を解決するために, 平面グラフをマイナー (縮約) という概念からアプローチしていました. その結果として, 平面グラフを二つの禁止マイナーによって特徴付けることに成功しました.

図6: 平面グラフを縮約しても平面グラフのままである.

ところで, 上の図から分かるように, 平面グラフは縮約操作に関して閉じているということが分かります. つまり平面グラフに対して縮約操作を行って得られたグラフもまた平面グラフです. 即ち平面グラフの全体はマイナーに関して閉じています.

　一般に, グラフ族 $\mathcal{G}$ に対して, 任意のグラフ $G \in \mathcal{G}$ に対して, $G$に縮約操作を行って得られるグラフもまた $\mathcal{G}$ に属するとき, $\mathcal{G}$ をマイナーに関して閉じている (minor closed) と言います.

　例えば $\mathcal{G}$ として「トーラスに埋め込むことの出来るグラフ全体」「射影平面に埋め込むことの出来るグラフ全体」などはマイナーに関して閉じています. これらのグラフは 禁止マイナーを使って特徴付けられるでしょうか？ つまりマイナーに関して閉じているようなグラフ族 $\mathcal{G}$ 及び任意のグラフ $G$に対し,

$G \in \mathcal{G}$ であることと $G$ は $X_1,\,X_2,\,\ldots$ をマイナーとして含まない ことは必要十分条件である.

となるようなグラフの集合 ${\bf X} := X_1,\,X_2,\,\ldots$ をとることは可能なのでしょうか？

$X$が無限集合でも良い場合は明らかに, ${\bf X}$ を $\mathcal{G}$に含まれないグラフの全体 とすることによって条件を満たすことが出来ます. でも平面グラフの場合は, ${\bf X}=\{K_5,\,X_{3,3}\}$ と有限集合で取ることが出来ました.

実は先ほどの例で挙げた 「トーラスに埋め込むことの出来るグラフ全体」「射影平面に埋め込むことの出来るグラフ全体」は有限個の禁止マイナーで特徴付けられることが証明されています. そこで出てきたのが次のWagner 予想 です.

予想 (Wagner)

マイナーに関して閉じているようなグラフ族は, 有限個の禁止マイナーで特徴付けることが出来る.

この予想はグラフ理論の難しい未解決問題として知られていました. しかしSeymour と Robertson の二人が 1984年に「木分解」と呼ばれる斬新なテクニックを用いてこの予想を肯定的に解決しました. この二人が示したのが次に示す主張で, 現在ではこの主張を「グラフマイナー定理」と呼ばれます.

定理 (Seymour, Robertson, 2004)

グラフの全体はマイナー順序によって, よい擬順序付けられている.

そしてこの定理と Wagner 予想 が同値であるので, めでたく Wagner 予想が肯定的に解決された, ということになります.

この二人は1984年に Wagner 予想の解決を発表してから 2004年まで, 通算で500ページにもわかる長大な論文を20年もかけて書き上げました. こうして証明されたグラフマイナー定理から得られる系は沢山あり, グラフ理論のみならず組合せ最適化の分野にも影響を及ぼしました.

4. グラフマイナー定理

　3章までがグラフマイナー定理の誕生の動機でしたが, 本章からはその内容について書いていきます.

4.1. マイナー順序

　数学においてはしばし「順序関係」という言葉が使われます. 一般には数の大小や単語の辞書式順序などの意味でよく使われると思いますが, 今回は グラフの順序 として, マイナー順序というのを考えます. 順序については こちらの記事 で用語の解説を書いています.

定義 (マイナー順序)

二つのグラフ $G,\,H$ に対し, $H$が$G$をマイナーとして含むとき, $G \preceq H$ と表す. この順序 $\preceq$ を マイナー順序と呼ぶ.

　全順序は以下の四つの公理を満たすような順序でした:

1. $a \preceq a$. (反射律)
2. $a \preceq b,\,b \preceq c$ ならば $a \preceq c$. (推移律)
3. $a \preceq b$ かつ $b \preceq a$ ならば, $a=b$ (反対称律)
4. 任意の $a,b$ に対して $a \preceq b$ もしくは $b \preceq a$ のどちらかが成り立つ (全順序律)

　しかしマイナー順序は全順序ではありません. 例えば $K_5$ と $K_{3,3}$ は一方が他方をマイナーとして含むようなことはないので, この順序では比較できません. このようなペアのことを 比較不能対 と呼ぶことにします. 有限グラフ上のマイナー順序は上に挙げた中で 1,2,3が成り立つので, この順序は半順序です. が, 今回では参考文献[2]に従って 擬順序 として考えることにします.

4.2. よい擬順序 (well-quasi-order)

　順序集合 $(X, \leq)$ で $\leq$ が擬順序 になっていて, 更に $X$ が無限集合であるようなものを考えます. 例えば $X$ として 平面グラフの全体, $\leq$ として マイナー順序 とするのが良いでしょう. $X$ 上の無限列 $(x_1,x_2,\ldots)$ を考えます. この列が よい列 (good) であるとは, あるインデックス $i<j$ が存在して $x_i \leq x_j$ となることをいいます. そして $X$ 上の任意の無限列が よい列 であるならば, $\leq$ は 良い擬順序 (well-quasi-order) といいます. また, 無限列 $(x_1,x_2,\ldots)$ が 反鎖 であるとは, この列に含まれる任意の二要素が比較不能であることをいいます.

　$(x_1,x_2,\ldots)$ が よい列 でないということは, 任意の $i<j$ に対して, $x_i > x_j$ もしくは $x_i$ と $x_j$ は比較不能 であるということです. 実は $\leq$ が $X$上で 良い擬順序であるための必要十分条件は, $X$は 狭義単調減少無限列 も  反鎖 も含まないことであるという定理が証明できます.

　少し例を挙げます.

• $X=\mathbb{Z}$, $\leq$ を通常の整数の大小関係としましょう. このとき $X$ 上の無限列として $(-1,-2,\ldots)$ という狭義単調減少無限列がとれるため, $\leq$ は よい擬順序ではありません.
• $X=\mathbb{N}$, $\leq$ を通常の自然数の大小関係としましょう. このとき $X$ 上の無限列 として 単調減少なものはとれません. もちろん $\leq$ は全順序なので, 反鎖も存在しません. 従って $\leq$ は $\mathbb{N}$ 上では良い擬順序になっています.

　これでグラフマイナー定理の言っていることが分かると思います. つまり $X$ をグラフの全体, $\leq$ をマイナー順序 として定義したときに, $\leq$ は $X$ 上で良い擬順序になっている, と言っています. 自然数の例と同様に, マイナーの順序で単調減少な無限列はとれないので, グラフマイナー定理を言い換えると「任意のグラフの無限列 $(G_1,G_2,\ldots)$ をもってきたときに, $G_j$ が $G_i$ をマイナーとして含む (すなわち $G_i \leq G_j$) なる $i<j$ が存在する」ということになるわけです.

5. 木に関するグラフマイナー定理

　$\mathcal{T}$ を 木の全体とします. 更に $T_1, T_2 \in \mathcal{T}$ に対し, $T_2$ が $T_1$ を位相的マイナーとして含む (即ち $T_2$ は $T_1$ の細分を部分グラフとして含む) ときに $T_1 \leq T_2$ として定義します. この章では 次の定理を紹介します.

定理 (Kruskal, 1960)

上で定義した $\leq$ は $\mathcal{T}$ 上でよい擬順序になっている.


　この定理はいわば「グラフマイナー定理の木ver」と見ることが出来ます. この証明は非常にトリッキーで面白いので, 興味がある方は是非調べて見てください[2].

　私自身はグラフマイナー定理の証明をちゃんと追ったわけではないのでいい加減なことは言えないのですが, その長大な証明の大筋は次のようなロジックに従っているとのことです[2].

1. グラフに対してその木っぽさ (木幅) を定義する.
2. 木幅が有限なグラフに対しては, 木ver のグラフマイナー定理の証明ロジックを何回か適用させる.
3. 木幅が大きくなってしまうグラフに対しては, 木幅が大きいという構造上の特徴を用いてなんとかする.

　この中でグラフの木っぽさという概念が非常に有用なものなので, それについては後日書きたいと思います.

[1]: J. Hopcroft, R. E. Tarjan, "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, 1974
[2]: R. Diestel, "Graph Theory", 2000

全順序・半順序・擬順序

概要

　数学では様々な順序を考えることがあります. 一番簡単な例で言うと実数の全体 $\mathbb{R}$ において, $x,y\in \mathbb{R}$に対し$y-x\geq 0$ を $x\leq y$と定義して順序集合$(\mathbb{R},\leq)$を考えることが多いです. 実数だけではなく, 例えばグラフ理論でも順序を考えたりすることがあります.
　本記事では, 順序の公理について述べ, 全順序・半順序・擬順序について一気に述べたのちに例を幾つか挙げたいと思います.

解説単語 : 擬順序(前順序), 半順序, 全順序

順序の定義

　集合 $E$ (有限でも無限でもよい) に対し, $R: E\times E \to \{0,1\}$ を 関係 と呼びます. 特に, $R(x,y)=1$となるときは $x R y$と書くことがあります. 例えば $E=\mathbb{R}$, 関係$R$ として 「$\leq$」 を考えるとこれは大小関係を表す関係になっています. また, 「$=$」 という関係も考えることが出来ます. これは等号の関係です. このように見ると, 関係というのは非常に抽象的なもので, 表現力が非常に高いものだということが分かると思います.

　関係 $R$ が, 集合 $E$ に対していわゆる「順序」を付与するような関係である(即ち大小関係を決定するような関係である)ならば, そのことを強調するために $R$を順序と呼び, $\leq$ などと記述します. そして組 $(E, \leq)$ のことを 順序集合と呼びます.

　順序 $\leq$ として, 次の性質を満たすものを考えましょう:

1. 任意の $a \in E$ に対して $a \leq a$ (反射律)
2. $a,b,c \in E$ が, $a\leq b$, $b \leq c$ ならば $a \leq c$である (推移律)
3. $a,b \in E$ が $a \leq b$, $b \leq a$ ならば $a=b$ である (反対称律)
4. 任意の $a,b\in E$ に対して $a \leq b$ もしくは $b \leq a$ のどちらかが必ず成り立つ (全順序律)

　例えば 実数における通常の順序を考えると1～4の全てを満たしていることが用意に分かります. このように, これら全ての条件を満たすような順序 $\leq$ を特に 全順序 (totally order) と呼び, 全順序$\leq$ に対して $(E, \leq)$ を 全順序集合 (partially ordered set) と呼びます. また, 1~3を満たすものは 半順序 (partially order) と呼び, 1と2を満たすものは 擬順序 (quasi order) と呼ばれます.

　まとめると

• 全順序 : 1~4 を満たす
• 半順序 : 1~3 を満たす
• 擬順序 : 1~2 を満たす

です. 注意されたいのは, 全順序は半順序でもあり, 擬順序でもあるということです. 

　さて, これらの三つの順序の概念について, 幾つかの例を挙げながら見ていきましょう.

例(i). 集合の包含関係

　$U$を空でない集合とし, $E=2^U$ としましょう. 即ち $E$ は$U$の部分集合族です. このとき, $A, B\in E$ はそれぞれ$U$の部分集合となっています. そして $A \subseteq B$ ならば $A \leq B$ と定義しましょう. さて, $(E,\leq )$ はどんな順序集合になっているでしょうか？

　例として $U=\{1,2,3,4,5\}$ としてみます. $A = \{1,2,3\},\,B=\{1,2,3,4\}$ のときは $A \leq B$ となりますが, $A=\{1,2,3\},\,B=\{2,3,4\}$のときは $A\leq B$ でも $B \leq A$ でもありません. 順序の公理のうち, 4だけが満たされないので, この順序は半順序となります. ちなみに $A \leq B$ でも $B \leq A$ でもない組$(A,B)$ のことを 比較不能対 と呼びます.

例(ii). ビッグオー

　$E$ として, 自然数から正実数への関数の全体 としましょう. すなわち $E := \mathbb{N}^{\mathbb{R}_{>}}$ とします. そして, $f, g\in E$ に対して, $f(n)=O(g(n))$ のときに $f\leq g$ と定義します.

　即ち, ある $m \in \mathbb{N}$ 及び 定数 $c>0$ が存在して, 任意の $n \geq m$ に対して $f(n) \leq c \cdot g(n)$ が成り立つ, というときに $f \leq g$ と書くのです.

　オーダーによって定められたこの関係$\leq$ は,

1. $f(n) = O(f(n))$ より, $f \leq f$ (反射律)
2. $f(n) = O(g(n)),\,g(n)=O(h(n))$ ならば, それぞれの定数を$m_1,c_1,m_2,c_2$ としたときに $m=max(m_1,m_2)$, $c=c_1 \cdot c_2$ ととれば, 任意の $n \geq m$ に対し $f(n) \leq c_1 \cdot g(n) \leq c_1 c_2 \cdot h(n)$ となるので, $f \leq h$ (推移律)

　となるので, 擬順序となっています. 更に, $f(n)=n^2,\,g(n)=n^2+1$ と定義すると, $f \neq g$ でありしかも $f \leq g$ かつ $g \leq f$ となっているため, 条件3を満たしません. 即ちこれは 擬順序だが半順序でない例 になっているわけです.

例(iii). 確率変数

　確率空間 $(\Omega,\,\mathcal{F},\,P)$ 上の二つの確率変数 $X,Y:\Omega \to \mathbb{R}$ が

任意の $x \in \mathbb{R}$ に対して $\mathrm{Pr}(X \geq x) \leq \mathrm{Pr}(Y \geq x)$

を満たすとき, $X \leq Y$ と定義します. (ちなみにこのとき $Y$ は $X$ を支配する (dominate) と言います)

　気持ちとしては 「$X\geq x$ となる確率よりも $Y \geq x$ となる確率の方が高い」ということなので, 「$X$ よりも $Y$ の方が 大きい値をとりやすい」ということになります. 例えば「表の出る確率が0.5 のコインを $n$ 回投げて, 表が出た回数」を $X$, 「表の出る確率が 0.7 のコインを $n$ 回投げて, 表が出た回数」を $Y$ とすると, 明らかに$Y$のコインの方が表が出やすいので, 直感的には $X \leq Y$ な気がしてきます. (実際にこれは確率論で使われる「カップリング」と呼ばれるテクニックを用いて鮮やかに示すことが出来ます)

1. $\mathrm{Pr}(X \geq x) = \mathrm{Pr}(X \geq x)$ なので, $X \leq X$.
2. 任意の$x,y\in \mathbb{R}$ に対して, $\mathrm{Pr}(X \geq x) \leq \mathrm{Pr}(Y \geq x)$, $\mathrm{Pr}(X \geq y) \geq \mathrm{Pr}(Y \geq y)$ ならば, 任意の$z \in \mathbb{R}$に対して $\mathrm{Pr}(X \geq z) \leq \mathrm{Pr}(Y \geq z) \leq \mathrm{Pr}(Z \geq z)$ となるので, 推移律も成り立ちます.

　一方で, 例えば「確率0.5で表が出るコインを $2n$ 回投げたとき, 前半の$n$回の中で表が出た回数を $X$, 後半の$n$回の中で表が出た回数を $Y$」としてみると, $X$と$Y$は同じ分布に従うので$X \leq Y$かつ$Y \leq X$なのですが, 確率変数としては異なるので, $X \neq Y$です(*).

(*): 「確率変数として異なる」という部分を細かく議論します. 確率変数とは $\Omega$ から 実数 への$\mathcal{F}$-可測写像なので, $X=Y$ ということは 任意の $\omega \in \Omega$ に対して$X(\omega)=Y(\omega)$ ということを意味しています. 今回のコイントスの例では標本集合$\Omega$を $\Omega = \{0,1\}^{2n}$ として, σ-集合体を $\mathcal{F}=2^{\Omega}$ として, 確率測度$P$を$\Omega$上の一様分布とします. (つまり任意の $\omega \in \Omega$ に対し $P(\omega)=1/2^{2n}$). そして $\omega = \{\omega_1,\omega_2,\ldots,\omega_{2n}\}\in \{0,1\}^{2n}$ に対して, $X(\omega)=\omega_1+\omega_2+\cdots+\omega_n$, $Y(\omega)=\omega_{n+1}+\omega_{n+2}+\cdots+\omega_{2n}$ と定義します. すると $X, Y$ はコイントスの例と同じ分布に従うような確率変数となっていて, 明らかに $X\neq Y$ となっています.

例(iv). 有向グラフ

　有向グラフ $G$ 上の 2頂点 $a,b$ で, $b$ から $a$ への有向パスが存在するとき, $a \leq b$ と定義します. 

1. $a$ から $a$ へは長さ0のパスがあると見なすので, $a \leq a$ です.
2. $a \leq b,\,b \leq c$ ならば, $c$ から $b$ をつたって $a$ にいたるパスがあるので, $a \leq c$ となります.

　従ってこの順序関係は 擬順序 となります. 更に, $G$ が DAG の場合は条件3も満たすので, 半順序となります. 更に$G$のトポロジカル順序が一意の場合は, 条件4も満たすので全順序となります.

有名な東大の問題

1998年の東大の後期入試の問題で、「大学入試史上で最も難しい問題」といわれているみたいですがグラフ理論の問題なので、解いてみることにします。

問題文にある二つの操作(白頂点の追加、辺の細分）をそれぞれ(I), (II)と記すことにします。

小さい例で試すと、
長さ$3n+2$のパスは生成できなくて、長さ$3n$もしくは$3n+1$のパスは生成できないっぽいので答えとしてはこれになることが簡単に予想できると思います。でも長さ$3n+2$のパスが生成できないことを示すのが難しいです。

少し考えて見ると, 長さ$3n+2$の白パスは、黒丸からスタートすれば生成できる、ということが分かります。
ここでいう「パス」とは一本になっているグラフのことで、色は何でも良いこととします。（細かいことですが、頂点にラベルは付いておらず、左右反転して得られるものは異なるパスであると約束します）

そこで、補題として

「黒丸から生成できるパス」の全体と「白丸から生成できるパス」の全体がdisjointであることを示せばよいことになります。（これが言えれば、黒丸から生成できるパスは白丸から生成できないことになるので証明が完了する)

この補題を示すために、パスに対して不変量を考えることにします。つまりパス$P$に対して, $f(P)$という値を考え、白丸から得られるパスの不変量$f(P_1)$と黒丸から得られるパスの不変量$f(P_2)$が、どんな$P_1,P_2$に対しても必ず$f(P_1)\neq f(P_2)$になるということが示すことが出来れば、白丸から得られてしかも同時に黒丸からも得られるようなパス$P$が存在しない、つまり補題が成り立つことが示せることになります。

細かい証明とかは省きますが、不変量として
$f(P)=(2^{m-1}\cdot x_1 + 2^{m-2}\cdot x_2 + \cdots + 2^0\cdot x_m + n)$ mod $3$.
というのを考えます。
ここで$n$はパス$P$の頂点数、$m$はパス$P$が含む黒頂点の個数、$x_i$はパスを横に並べて書いたときに右から$i$番目にある黒頂点の座標(1-indexで考えていて、例えば1番右なら1, 右から2番目なら2, $\ldots$)です。

ローリングハッシュみたいな形の式をしていますが、この不変量を考えると
$P$が白丸から生成されるときは必ず $f(P)\in \{0,1\}$
$P$が黒丸から生成されるときは必ず $f(P) = 2$
となること分かり、証明が完了します。

不変量となっていることの証明は、操作(I), (II)それぞれの逆操作を考えて帰納法を使えばいけます。