クリーク

共通の点 $x$ があれば、$K$ のどの 2 区間も $x$ を含むので交わり、$K$ はクリークである。逆に $K$ をクリークとする。$u,v\in K$ について $a_u\le b_v$ である。$u=v$ なら区間の定義から、$u\ne v$ なら共通の点 $y$ について $a_u\le y\le b_v$ だからである。$a:=\max_{u\in K}a_u$ とおくと、各 $v\in K$ について $a_v\le a\le b_v$ なので $a\in I_v$ であり、$a$ は $K$ のすべての区間の共通の点である。
後半：各 $x$ について $\{v\mid x\in I_v\}$ は共通の点 $x$ をもつのでクリーク（空集合でもクリーク）であり、その頂点の個数は $\omega(G)$ 以下である。逆に最大クリーク $K$（$V\ne\emptyset$ なので空でない）には共通の点 $x$ があり、$\omega(G)=\lvert K\rvert\le\lvert\{v\mid x\in I_v\}\rvert$ である。右辺の値は有限個しかないので最大値がある。$\square$

1：クリークの条件は「含まれる相異なる 2 頂点がつねに隣接する」なので、部分集合でも成り立つ。$G[W]$ で 2 頂点が隣接することは $G$ で隣接することと同じなので、後半も成り立つ。
2：$K$ に属さない $w$ が $K$ のすべての頂点と隣接すれば $K\cup\{w\}$ はクリークで、$K$ は極大でない。逆に $K\subsetneq K'$ となるクリーク $K'$ があれば、$w\in K'\setminus K$ は $K$ のすべての頂点と隣接する。
3：$\overline G$ では相異なる 2 頂点が隣接することと $G$ で隣接しないことが同じなので、定義から従う。
4：$\omega(G)\ge1$ である。最大クリーク $K$ の頂点 $v$ は $K$ のほかの $\omega(G)-1$ 個の頂点と隣接するので、$\omega(G)-1\le d(v)\le\Delta(G)$ である。$\square$

補グラフ $\overline G$ の次数は $d_{\overline G}(v)=n-1-d(v)$、辺の本数は $\overline m:=\binom n2-m$ である（補グラフ の記事の命題「補グラフの基本性質」の 2）。Turánの定理 の記事の命題「次数による独立集合の下界」を $\overline G$ に当てはめ、prop-clq-basic の 3 を使うと
$$ \omega(G)=\alpha(\overline G)\ge\sum_{v\in V}\frac1{d_{\overline G}(v)+1}=\sum_{v\in V}\frac1{n-d(v)}\ge\frac{n^2}{2\overline m+n}=\frac{n^2}{n^2-2m} $$
である。$m>(1-\frac1r)\frac{n^2}2$ なら $n^2-2m<\frac{n^2}r$ なので右辺は $r$ より大きく、$\omega(G)$ は整数だから $\omega(G)\ge r+1$ である。$\square$

1：極大クリーク $K$ が $S_v$ と交わらなければ $K\subset N(v)$ で、$v\in S_v$ なので $v\notin K$ である。$K$ のすべての頂点が $v$ と隣接するので $K\cup\{v\}$ はクリークになり、$K$ の極大性に反する。
2：$K\setminus\{u\}$ の頂点は $u$ と隣接するので $N(u)$ に含まれ、$G[N(u)]$ のクリークである。極大であることを示す。$K\setminus\{u\}\subsetneq K'$ となる $G[N(u)]$ のクリーク $K'$ があれば、$K'$ の頂点はすべて $u$ と隣接するので $K'\cup\{u\}$ は $G$ のクリークで、$K$ を真に含む。これは $K$ の極大性に反する。$K=(K\setminus\{u\})\cup\{u\}$ なので、この写像は単射である。$\square$

$s=1$ のとき $3^{-1/3}<1$。$s=2$ のとき、$2^3=8<9=3^2$ より $2<3^{2/3}$。$s=3$ のとき値は $1$ である。$s\ge3$ なら $\frac{s+1}s\le\frac43$ で、$\bigl(\frac43\bigr)^3=\frac{64}{27}<3$ より $\frac{s+1}s<3^{1/3}$ なので、$(s+1)3^{-(s+1)/3}< s\cdot3^{-s/3}$ である。よって $s\ge4$ で値は $1$ より小さい。$\square$

$n$ についての帰納法で示す。$n=0$ なら $M(G)=1=3^0$ である。$n\ge1$ とし、$n$ 未満の頂点数のグラフでは成り立つとする。次数が最大の頂点 $v$ をとり、$\Delta:=d(v)$、$S_v:=V\setminus N(v)$ とおく。$\lvert S_v\rvert=n-\Delta\ge1$ である。
lem-clq-counting の 1 により、どの極大クリークも $S_v$ のある頂点 $u$ を含む。$u$ を含む極大クリークの個数は、同じ補題の 2 により $M(G[N(u)])$ 以下である。$G[N(u)]$ の頂点は $d(u)\le\Delta\le n-1$ 個なので、帰納法の仮定と、$3^{x/3}$ が $x$ について増加することから $M(G[N(u)])\le3^{d(u)/3}\le3^{\Delta/3}$ である。$S_v$ の頂点について足し合わせると、$s:=n-\Delta$ として
$$ M(G)\ \le\ \sum_{u\in S_v}M(G[N(u)])\ \le\ s\cdot3^{(n-s)/3}\ =\ 3^{n/3}\cdot s\cdot3^{-s/3}\ \le\ 3^{n/3} $$
である。最後の不等号は lem-clq-elementary による。
$n=3k$ のとき、$K_{3,\dots,3}$（$k$ 個の部分）の極大クリークは各部分から 1 頂点ずつ選んだ集合なので（ex-clq-basic の 3）、$M=3^k=3^{n/3}$ である。$\square$

$\lvert P\rvert$ についての帰納法で示す。$R\subset K\subset R\cup P$ を満たす極大クリーク $K$ の全体を $\mathcal F(R,P)$ と書く。
$P=\emptyset$ の場合。手順 2 では何も行わない。$X=\emptyset$ なら $C(R)=\emptyset$ なので $R$ に加えられる頂点はなく、$R$ は極大クリークで、$\mathcal F(R,\emptyset)=\{R\}$ である。手順 1 は $R$ を 1 回出力する。$X\ne\emptyset$ なら $X$ の頂点を $R$ に加えられるので $R$ は極大でなく、$\mathcal F(R,\emptyset)=\emptyset$ である。手順 1 は何も出力しない。
$P\ne\emptyset$ の場合。手順 1 は何も出力せず、$P$ の頂点は $C(R)$ に属するので $R$ は極大でない。手順 2 で取り出す順に $P=\{v_1,\dots,v_k\}$ とし、$P_i:=P\setminus\{v_1,\dots,v_{i-1}\}$、$X_i:=X\cup\{v_1,\dots,v_{i-1}\}$ とおく。$i$ 番目に行う手続きは $\mathrm{BK}(R_i,P_i',X_i')$、ただし $R_i:=R\cup\{v_i\}$、$P_i':=P_i\cap N(v_i)$、$X_i':=X_i\cap N(v_i)$ である。
まず、この呼び出しが定理の仮定を満たすことを確かめる。$v_i\in C(R)$ なので $R_i$ はクリークである。$w\notin R_i$ が $R_i$ のすべての頂点と隣接することは、$w\in C(R)$ かつ $w\in N(v_i)$ であることと同じである（$v_i\notin N(v_i)$ なので $w\ne v_i$ は自動的に成り立つ）。$P_i\cup X_i=P\cup X=C(R)$ なので $C(R_i)=(P_i\cup X_i)\cap N(v_i)=P_i'\cup X_i'$ であり、$P_i'$ と $X_i'$ は交わらず、どちらも $R_i$ と交わらない。$v_i\notin P_i'$ なので $\lvert P_i'\rvert<\lvert P\rvert$ であり、帰納法の仮定により、$i$ 番目の呼び出しは有限回で終わり、$\mathcal F(R_i,P_i')$ の元をちょうど 1 回ずつ出力し、それ以外は出力しない。
あとは、$\mathcal F(R,P)$ が $\mathcal F(R_1,P_1'),\dots,\mathcal F(R_k,P_k')$ の互いに交わらない和であることを示せばよい。$K\in\mathcal F(R,P)$ とする。$R$ は極大でないので $K\ne R$ であり、$K\setminus R$ は $P$ の空でない部分集合である。$v_i\in K$ となる最小の $i$ をとる。$K\setminus R$ の $v_i$ 以外の頂点は、$P$ に属し、$i$ の最小性から $v_1,\dots,v_{i-1}$ のどれでもないので $P_i$ に属し、$K$ がクリークなので $v_i$ と隣接する。よって $R_i\subset K\subset R_i\cup P_i'$、すなわち $K\in\mathcal F(R_i,P_i')$ である。逆に $K\in\mathcal F(R_i,P_i')$ なら $R\subset K\subset R\cup P$ で $K\in\mathcal F(R,P)$ であり、$K\cap\{v_1,\dots,v_k\}$ の最小の添字は $i$ である（$K\setminus R$ の頂点は $v_i$ か $P_i$ の頂点で、$P_i$ は $v_1,\dots,v_{i-1}$ を含まない）。したがって $K$ を含む $\mathcal F(R_i,P_i')$ はただ 1 つで、$K$ はちょうど 1 回出力される。
最後の主張：$R=X=\emptyset$、$P=V$ は仮定を満たし（$C(\emptyset)=V$）、$\mathcal F(\emptyset,V)$ は $G$ の極大クリーク全体である。$\square$