誘導部分グラフ

1：$H$ は部分グラフなので $E(H)\subset E\cap[V(H)]^2$ である。条件は逆向きの包含 $E\cap[V(H)]^2\subset E(H)$ と同値であり、両方合わせて $H=G[V(H)]$ となる。
2：両辺の頂点集合は $U$ で、辺集合は $(E\cap[W]^2)\cap[U]^2=E\cap[U]^2$ である（$[U]^2\subset[W]^2$）。$G[W][U]\cong F$ なら $G[U]\cong F$ なので、$G[W]$ が $F$ を含み、$G$ が $G[W]$ を含むとき、$G$ は $F$ を含む。
3：$f$ の制限は $W$ から $f(W)$ への全単射であり、相異なる $u,v\in W$ について $uv\in E\cap[W]^2\iff uv\in E\iff f(u)f(v)\in E'\iff f(u)f(v)\in E'\cap[f(W)]^2$ である。
4：補グラフ の記事の命題「補グラフの基本性質」の 4 により $\overline G[W]=\overline{G[W]}$ であり、同じ命題の 5 により $G[W]\cong F\iff\overline{G[W]}\cong\overline F$ である。逆向きは $\overline{\overline G}=G$ による。$\square$

$\operatorname{Forb}(\mathcal F)$ は遺伝的である：同型で閉じていることは prop-is-basic の 3 による。$G\in\operatorname{Forb}(\mathcal F)$ の誘導部分グラフ $G[W]$ がある $F\in\mathcal F$ を含めば、prop-is-basic の 2 により $G$ も $F$ を含むので矛盾する。これで 1 の「$\Rightarrow$」が示された。
$\mathcal P$ を遺伝的とし、$\mathcal P=\operatorname{Forb}(\mathcal M(\mathcal P))$ を示す。$G\in\mathcal P$ なら、$G$ の誘導部分グラフはすべて $\mathcal P$ に属し、$\mathcal M(\mathcal P)$ の元は $\mathcal P$ に属さない。$\mathcal P$ は同型で閉じているので、$G$ は $\mathcal M(\mathcal P)$ の元を誘導部分グラフとして含まない。逆に $G\notin\mathcal P$ とする。$G[W]\notin\mathcal P$ となる $W\subset V(G)$（$W=V(G)$ がその例）のうち、元の個数が最小のものをとる。$G[W]$ の真の誘導部分グラフは $G[U]$（$U\subsetneq W$、prop-is-basic の 2）の形であり、$W$ の最小性から $\mathcal P$ に属する。よって $G[W]\in\mathcal M(\mathcal P)$ であり、$G$ は $\mathcal M(\mathcal P)$ の元を含む。これで $\mathcal P=\operatorname{Forb}(\mathcal M(\mathcal P))$ が示され、1 の「$\Leftarrow$」も得られた。
最後に $\mathcal P=\operatorname{Forb}(\mathcal F)$ とし、$M\in\mathcal M(\mathcal P)$ をとる。$M\notin\mathcal P$ なので、ある $F\in\mathcal F$ と $W\subset V(M)$ で $M[W]\cong F$ となる。$W\neq V(M)$ とすると、$v\in V(M)\setminus W$ をとれば $M[W]$ は $M-v$ の誘導部分グラフなので、$M-v$ は $F$ を含む。ところが $M-v$ は $M$ の真の誘導部分グラフなので $\mathcal P=\operatorname{Forb}(\mathcal F)$ に属し、矛盾する。よって $W=V(M)$ で $M\cong F$ である。$\square$

$C\colon v_0,v_1,\dots,v_{\ell-1},v_0$ を長さ $\ell$ が最小の奇閉路とし、$W=\{v_0,\dots,v_{\ell-1}\}$ とする。$G[W]$ が $C$ の辺以外の辺 $v_iv_j$（$0\le i< j\le\ell-1$、$2\le j-i\le\ell-2$）をもつとする。この弦で $C$ を 2 つに分けると、
$$v_i,v_{i+1},\dots,v_j,v_i\qquad\text{と}\qquad v_j,v_{j+1},\dots,v_{\ell-1},v_0,\dots,v_i,v_j$$
はそれぞれ長さ $j-i+1$ と $\ell-(j-i)+1$ の閉路である。どちらの長さも $3$ 以上 $\ell-1$ 以下で、和は $\ell+2$（奇数）なので、一方は奇数である。これは $\ell$ の最小性に反する。よって $G[W]$ の辺は $C$ の辺だけであり、$G[W]\cong C_\ell$ である。長さの偶奇を問わない場合も、同じ分割で得られる 2 つの閉路はどちらも $C$ より短いので、同じ議論が成り立つ。$\square$

1：二部グラフ の記事の定理「閉路の長さによる特徴付け」により、$G$ が二部グラフであることは奇閉路をもたないことと同値である（BM76 Theorem 1.2、p. 14）。奇閉路をもたなければ誘導された奇閉路ももたない。逆に奇閉路をもてば、lem-is-shortest-cycle により長さが奇数の誘導閉路をもつ。これで同値性が示された。すなわち二部グラフ全体は $\operatorname{Forb}(\{C_3,C_5,\dots\})$ である。奇閉路グラフ $C_{2k+1}$ は二部グラフでなく、1 頂点を除くと道になり、道は二部グラフである（頂点を交互に分ければよい）。よって $C_{2k+1}\in\mathcal M$ である。逆に thm-is-forbidden の 2 により、$\mathcal M$ の各元は奇閉路グラフのどれかと同型である。
2：閉路をもたなければ誘導閉路ももたず、閉路をもてば lem-is-shortest-cycle により誘導閉路をもつ。$C_k$ は閉路をもち、1 頂点を除くと道になって閉路をもたない。あとは 1 と同じである。$\square$

頂点数 $n$ についての帰納法で示す。$n=2$ なら、2 頂点が隣接すれば $\overline G$ が、隣接しなければ $G$ が連結でない。$n\ge3$ とし、$n-1$ 頂点では成り立つとする。頂点 $v$ を 1 つとる。$G-v$ は $P_4$-free で（prop-is-basic の 2）$n-1\ge2$ 頂点なので、帰納法の仮定により $G-v$ か $\overline{G-v}$ が連結でない。$\overline{G-v}=\overline G-v$ であり（補グラフ の記事の命題「補グラフの基本性質」の 4）、$\overline G$ も $P_4$-free で、結論は $G$ と $\overline G$ について対称である。したがって、必要なら $G$ を $\overline G$ に取り替えて、$H:=G-v$ が連結でないとしてよい。
$G$ が連結でなければ示すことはないので、$G$ は連結とする。このとき $H$ の各連結成分には $v$ の隣接頂点がある。実際、$v$ の隣接頂点を含まない $H$ の連結成分 $C$ があれば、$C$ の頂点と $C$ の外の頂点を結ぶ $G$ の辺はなく、$G$ は連結でない。
$v$ が $H$ のすべての頂点に隣接するとし、$\overline G$ が連結でないことを示す。このとき $v$ は $\overline G$ で孤立点であり、$n\ge2$ なので $\overline G$ は連結でない。
残りは、$v$ に隣接しない頂点 $x\in V(H)$ がある場合で、これが起こらないことを示す。$x$ を含む $H$ の連結成分 $C$ をとる。$C$ には $v$ の隣接頂点 $y_0$ がある。$C$ は連結なので、$C$ の中の道 $y_0,y_1,\dots,y_m=x$ がある。$y_0$ は $v$ に隣接し $y_m$ は隣接しないので、$y_{i}$ が $v$ に隣接し $y_{i+1}$ が隣接しない $i$ がある。$y:=y_i$、$x':=y_{i+1}$ とおく。$H$ は連結でないので、$C$ と異なる連結成分 $D$ があり、$D$ には $v$ の隣接頂点 $z$ がある。4 頂点 $z,v,y,x'$ について、$zv$、$vy$、$yx'$ は辺であり、$zy$ と $zx'$ は $H$ の異なる連結成分の頂点どうしなので辺でなく、$vx'$ は辺でない。よって $G[\{z,v,y,x'\}]$ は道 $z,v,y,x'$ と同型で、$G$ が $P_4$-free であることに反する。$\square$

$P_4$-free なグラフ全体が 1 頂点のグラフを含み、3 つの操作で閉じていることを示せば、$\mathcal C$ の最小性から $\mathcal C$ の元は $P_4$-free である。同型で閉じていることは prop-is-basic の 3、補グラフで閉じていることは上で見た。$G_1,G_2$ が $P_4$-free なら、非交和 $G_1\cup G_2$ の誘導部分グラフ $G[W]$ は $G_1[W\cap V(G_1)]\cup G_2[W\cap V(G_2)]$ であり、$W$ が両側と交わればこれは連結でない。$P_4$ は連結なので、$P_4$ と同型な $G[W]$ は一方の側に収まり、$G_1$ か $G_2$ が $P_4$ を含むことになって矛盾する。
逆に、$P_4$-free なグラフ $G$ が $\mathcal C$ に属することを頂点数の帰納法で示す。1 頂点なら定義による。2 頂点以上なら、thm-is-p4-free により $G$ か $\overline G$ が連結でない。$G$ が連結でないとき、1 つの連結成分の頂点集合を $S$ とすると、$S$ と $V\setminus S$ を結ぶ辺はないので $G=G[S]\cup G[V\setminus S]$ であり、両者は頂点の少ない $P_4$-free なグラフなので $\mathcal C$ に属し、$G\in\mathcal C$ である。$\overline G$ が連結でないときは、同じ議論で $\overline G\in\mathcal C$（$\overline G$ も $P_4$-free）となり、$G=\overline{\overline G}\in\mathcal C$ である。$\square$

頂点数の帰納法による。0 頂点なら両辺は $0$、1 頂点なら両辺は $1$ である。2 頂点以上とし、cor-is-cograph の証明のとおり、$G=G_1\cup G_2$（非交和）か、$\overline G$ が連結でなく $G=G_1+G_2$（結合、補グラフ の記事の系「補グラフが連結でないグラフ」）と、頂点の少ない $P_4$-free なグラフ $G_1,G_2$ で書ける。帰納法の仮定により $\chi(G_i)=\omega(G_i)$ である。
非交和の場合：2 頂点以上のクリークは連結なので一方の側に収まり、$\omega(G)=\max_i\omega(G_i)$ である。$G_1,G_2$ をそれぞれ $\max_i\chi(G_i)$ 色以内で塗れば $G$ の彩色になり、$\chi(G)\le\max_i\chi(G_i)=\max_i\omega(G_i)=\omega(G)\le\chi(G)$ である。
結合の場合：$G_1$ のクリークと $G_2$ のクリークの和はクリークであり、$G$ のクリークはそれぞれの側でクリークなので、$\omega(G)=\omega(G_1)+\omega(G_2)$ である。$G$ の彩色では、$V(G_1)$ の頂点と $V(G_2)$ の頂点はすべて隣接するので、両側で使う色は共通でない。各側への制限はその側の彩色なので $\chi(G)\ge\chi(G_1)+\chi(G_2)$ であり、両側を別々の色で塗れば等号が成り立つ。よって $\chi(G)=\chi(G_1)+\chi(G_2)=\omega(G_1)+\omega(G_2)=\omega(G)$ である。$\square$