グラフマイナー

（$\Rightarrow$）$G'$ が $G$ から操作を 1 回行って得られ、$G'$ の中に $H$ のモデル $(W_x)$ があれば、$G$ の中にも $H$ のモデルがあることを示す。$G'=G-v$ または $G-e$ なら $G'$ は $G$ の部分グラフで、$(W_x)$ がそのまま $G$ の中のモデルになる（連結性と辺の存在は辺を増やしても保たれる）。$G'=G/e$、$e=uv$ とする。$v_e$ を含む $W_{x_0}$ があれば、それを $W_{x_0}':=(W_{x_0}\setminus\{v_e\})\cup\{u,v\}$ に、ほかの $W_x$ はそのままにする。$G/e$ の辺で $v_e$ に接続する辺 $v_ew$ は $G$ の辺 $uw$ か $vw$ から来ており、$u,v$ は隣接するので、$G[W_{x_0}']$ は連結である。分岐集合どうしを結ぶ辺も同じ理由で $G$ の辺に置き換わる。$v_e$ がどの $W_x$ にも属さなければ $(W_x)$ はそのまま $G$ の中のモデルである。$H$ と同型なグラフ $H'$ には 1 点集合からなるモデルがあり、同型で $H$ のモデルに移せる。操作の回数についての帰納法で、$G$ の中に $H$ のモデルがある。

（$\Leftarrow$）モデル $(V_x)$ をとる。まず $\bigcup_xV_x$ の外の頂点を除き、次に $x\ne y$、$xy\notin E(H)$ である $V_x$ と $V_y$ を結ぶ辺を除く。各 $G[V_x]$ の全域木（連結だからある）の辺を 1 本ずつ縮約していくと、縮約のたびに $V_x$ の像は 1 点ずつ減り、連結のままなので、最後には各 $V_x$ が 1 頂点 $x$ になる。$V_x$ の中の残りの辺は両端が 1 点にまとまった時点で消える。得られたグラフの頂点は $V(H)$ と対応し、$x,y$ が隣接するのは $V_x$ と $V_y$ を結ぶ辺が残っていたとき、すなわち $xy\in E(H)$ のときに限る（モデルの条件 3 によりそのような辺は必ずある）。よって $H$ と同型なグラフが得られた。$\square$

1：$G\in\operatorname{Forb}(\mathcal X)$、$H\preceq G$ とする。$H$ が $X\in\mathcal X$ をマイナーとして含めば、推移性により $G$ も $X$ を含むので矛盾する。

2：$G\in\mathcal P$ が $K\in\mathcal K(\mathcal P)$ をマイナーとして含めば、マイナー閉なので $K\in\mathcal P$ となって矛盾する。よって $\mathcal P\subset\operatorname{Forb}(\mathcal K(\mathcal P))$。逆に $G\notin\mathcal P$ とする。$G$ のマイナーで $\mathcal P$ に属さないもの（$G$ 自身がそうである）のうち、$\lvert\cdot\rvert+e(\cdot)$ が最小のもの $K$ をとる。$K$ の真のマイナー $K'$ は prop-gm-order の 2 の証明により $\lvert K'\rvert+e(K')$ がより小さく、$G$ のマイナーでもあるので $K'\in\mathcal P$ である。よって $K\in\mathcal K(\mathcal P)$ で、$G\notin\operatorname{Forb}(\mathcal K(\mathcal P))$ である。

3：$K\in\mathcal K(\mathcal P)$ は $\mathcal P$ に属さないので、ある $X\in\mathcal X$ をマイナーとして含む。$X\preceq X$ なので $X\notin\mathcal P$ であり、$K$ の真のマイナーはすべて $\mathcal P$ に属するから、$X$ は $K$ の真のマイナーではない。よって $X$ は $K$ と同型である。$K,K'\in\mathcal K(\mathcal P)$ で $K$ が $K'$ の真のマイナーなら $K\in\mathcal P$ となり矛盾する。$\square$

閉路をもつグラフは ex-gm-cycles により $K_3$ をマイナーとして含む。逆に、森のマイナーが森であることを示す。森から頂点や辺を除いても森である。森 $G$ の辺 $e=uv$ を縮約した $G/e$ が閉路 $C$ をもつとする。$C$ が $v_e$ を通らなければ $C$ は $G$ の閉路である。$C$ が $v_e$ を通るとき、$C$ の上で $v_e$ に隣り合う 2 頂点を $a\ne b$ とし、$C$ から $v_e$ を除いた $a$ から $b$ への道を $P$ とする。$a$ は $G$ で $u$ か $v$ に隣接し、$b$ も同様である。$a$ と $b$ が同じ頂点、たとえば $u$ に隣接すれば $a\,P\,b\,u\,a$ が、$a$ が $u$ に、$b$ が $v$ に隣接すれば $a\,P\,b\,v\,u\,a$ が $G$ の閉路になる（$u,v$ は $P$ の上にない）。どちらも $G$ が森であることに反する。よって森の族はマイナー閉で、$K_3$ は森でないので森は $K_3$ をマイナーとして含まない。

後半：prop-gm-order の 3 により、$K_3$ の真のマイナーは $K_3-v=K_2$、$K_3-e$（長さ $2$ の道）、$K_3/e=K_2$ のどれかのマイナーで、これらは森なので森である。よって $K_3\in\mathcal K(\text{森})$ であり、prop-gm-forbidden の 3 により $\mathcal K(\text{森})$ の元はすべて $K_3$ と同型である。$\square$

1：$v\in V_s\cap V_{s'}$、$s\in T_1$、$s'\in T_2$ なら、$s$ と $s'$ を結ぶ $T$ の道は $t_1,t_2$ を通るので、(T3) により $v\in V_{t_1}\cap V_{t_2}$ である。逆の包含は明らかである。$x\in U_1\setminus U_2$、$y\in U_2\setminus U_1$ を結ぶ辺があれば、(T2) により $x,y$ をともに含む袋 $V_s$ があり、$s\in T_1$ なら $y\in U_1$、$s\in T_2$ なら $x\in U_2$ となって矛盾する。

2：$W$ が $U_1\cap U_2$ と交わらなければ、(T1) により $W$ は $W\cap(U_1\setminus U_2)$ と $W\cap(U_2\setminus U_1)$ に分かれ、仮定から両方とも空でなく、1 によりその間に辺がない。これは $G[W]$ の連結性に反する。

3：完全な部分グラフの頂点集合を $K$ とする。$T$ の各辺 $t_1t_2$ について、1 により $K$ の頂点が $U_1\setminus U_2$ と $U_2\setminus U_1$ の両方にあることはない（あればその 2 頂点は隣接する）ので、$K\subset U_1$ または $K\subset U_2$ である。$K\subset U_i$ となる $i$ を 1 つ選び、辺を $t_i$ に向ける。ノードから出る向きの辺があればそれをたどることを繰り返すと、木の中で同じ辺を逆にたどることはないので道になり、いつか止まる。止まったノード $t$ では、$t$ に接続するどの辺も $t$ に向いている。$w\in K$ をとり、$w\in V_s$ とする。$s\ne t$ なら、$t$ から $s$ への道の最初の辺 $tt'$ は $t$ に向いているので、$w$ は $t$ の側のあるノード $s'$ の袋にも属する。$t$ は $s'$ と $s$ を結ぶ道の上にあるので、(T3) により $w\in V_t$ である。よって $K\subset V_t$ である。$\square$

1：$G$ の木分解 $(T,(V_t))$ と、$G$ の中の $H$ のモデル $(V_x)_{x\in V(H)}$（prop-gm-equivalent）をとり、$W_t:=\{x\in V(H)\mid V_x\cap V_t\ne\emptyset\}$ とおく。分岐集合は互いに交わらないので $\lvert W_t\rvert\le\lvert V_t\rvert$ である。$(T,(W_t))$ が $H$ の木分解であることを示す。(T1)：$V_x$ は空でなく、その頂点はある袋に属する。(T2)：$H$ の辺 $xy$ について $V_x$ と $V_y$ を結ぶ辺 $ab$ があり、$a,b$ をともに含む袋 $V_t$ について $x,y\in W_t$ である。(T3)：$x\in W_{t_1}\cap W_{t_3}$ で、$t_2$ が $t_1$ と $t_3$ を結ぶ道の上にあるとする。$t_2\ne t_1,t_3$ としてよい。その道の上で $t_2$ に隣り合い $t_1$ の側にあるノードを $s$ とし、辺 $st_2$ について lem-gm-separation の記号で $s$ の側を $U_1$、$t_2$ の側を $U_2$ とする。$V_x$ は $V_{t_1}\subset U_1$ とも $V_{t_3}\subset U_2$ とも交わり、$G[V_x]$ は連結なので、lem-gm-separation の 2 により $V_x$ は $V_s\cap V_{t_2}\subset V_{t_2}$ と交わる。よって $x\in W_{t_2}$ である。

2：袋が $V(K_n)$ だけの木分解（$T$ は 1 点）の幅は $n-1$ である。逆に lem-gm-separation の 3 によりどの木分解にも $V(K_n)$ を含む袋があるので、幅は $n-1$ 以上である。

3：$G$ が木で頂点が 2 個以上のとき、$T$ のノードを $G$ の頂点と辺の全体とし、頂点 $v$ と辺 $e$ を $v$ が $e$ の端点のとき結ぶ（$T$ は $G$ の各辺の中点に頂点を置いたグラフで、木である）。袋を $V_v:=\{v\}$、$V_e:=\{u,v\}$（$e=uv$）とすると、(T1)(T2) は明らかで、$T_v$ は $v$ と $v$ に接続する辺からなる星形の部分木なので (T3) も成り立つ。幅は $1$ である。頂点が 1 個の木には 1 点の袋 1 つの木分解がある。森なら、各成分の木分解の木を辺で 1 本の木につなげばよい（成分ごとの袋は互いに交わらないので (T3) は保たれる）。逆に $\operatorname{tw}(G)\le1$ なら、1 と 2 により $\operatorname{tw}(K_3)=2$ なので $G$ は $K_3$ をマイナーとして含まず、thm-gm-forest により森である。

4：頂点を $v_1,\dots,v_n$ と並べ、$T$ を $n-2$ 個のノード $t_2,\dots,t_{n-1}$ の道とし、$V_{t_i}:=\{v_1,v_i,v_{i+1}\}$ とする。辺 $v_1v_2$ は $V_{t_2}$ に、辺 $v_iv_{i+1}$（$2\le i\le n-1$）は $V_{t_i}$ に、辺 $v_nv_1$ は $V_{t_{n-1}}$ に含まれ、$v_1$ はすべての袋に、$v_i$（$2\le i\le n$）は隣り合う高々 2 つの袋に属するので (T3) も成り立つ。よって $\operatorname{tw}(C_n)\le2$ で、$C_n$ は森でないので 3 により $\operatorname{tw}(C_n)\ge2$ である。

5：1 と 2 による（$\operatorname{tw}(K_4)=3$）。$\square$