§E16.9Turán の定理

証明.$S=\{(u,v)\in A\times B:\ uv\in E\}$と置く。§E16.6 命題 2.1を$X=A$、$Y=B$および上の$S$に対して適用する。$u\in A$に対する切り口は$S_u=\{v\in B:\ uv\in E\}=N_G(u)\cap B$であり、$v\in B$に対する切り口は$S^{v}=\{u\in A:\ uv\in E\}=N_G(v)\cap A$である。ゆえに$\lvert S\rvert=\sum_{u\in A}\lvert N_G(u)\cap B\rvert=\sum_{v\in B}\lvert N_G(v)\cap A\rvert$が成り立つ。

残るのは$\lvert S\rvert=\lvert E(A,B)\rvert$の一手である。写像$\Psi(u,v)=\{u,v\}$は$S$から$E(A,B)$への写像である。$A\cap B=\varnothing$であるから、$E(A,B)$の各辺は$A$に属する端点と$B$に属する端点をちょうど一つずつもつ。ゆえに$\Psi(u,v)=\Psi(u',v')$ならば$u=u'$かつ$v=v'$であって$\Psi$は単射であり、また$E(A,B)$の各辺はその二つの端点の組の像として得られるから$\Psi$は全射である。§D2.2 命題 1.5より$\lvert S\rvert=\lvert E(A,B)\rvert$である。▨

証明. 主張 (1)の存在.$r$個の非負整数のうち$s$個を$q+1$、残る$r-s$個を$q$と定めると、その総和は$s(q+1)+(r-s)q=qr+s=n$である。値は$q$と$q+1$の二種類だけであるから、どの二つの差も$1$以下である。$n$元集合をこの大きさの部へ分ける分割は、$n$元集合の元を順に並べて先頭から順に切り分けることで得られる。ゆえに条件を満たす分割が存在する。

主張 (1)の一意性.定義 2.2の条件を満たす分割の部の大きさを$n_1,\dots,n_r$とし、$q'=\min_i n_i$と置く。条件より各$n_i$は$q'$以上$q'+1$以下であるから、$n_i\in\{q',q'+1\}$である。$n_i=q'+1$である添字の個数を$s'$とすると$n=rq'+s'$である。最小値を取る添字が少なくとも一つ存在するから$s'\le r-1$であり、$0\le s'\le r-1$である。除法の一意性より$q'=q$かつ$s'=s$である。

主張 (2)を示す。$T(n,r)$の頂点集合を$V$とし、$S\subseteq V$を$\lvert S\rvert=r+1$とする。$S$の各頂点を、それが属する部へ対応させると、$r+1$個の対象を$r$個の部へ入れることになるから、§D2.3 系 4.3より同じ部に属する相異なる二頂点が存在する。この二頂点は隣接しないので$S$はクリークではない。ゆえに$T(n,r)$は$(r+1)$元クリークをもたない。

主張 (3)を示す。$n\le r$のとき$q=\lfloor n/r\rfloor$は$n<r$ならば$0$、$n=r$ならば$1$である。前者では$s=n$であるから大きさ$1$の部が$n$個、大きさ$0$の部が$r-n$個であり、後者では$s=0$であるから大きさ$1$の部が$r=n$個である。いずれの場合も、空でない部はすべて一元であるから、相異なる二頂点はつねに相異なる部に属し、すべての対が辺になる。ゆえに$T(n,r)\cong K_n$である。

主張 (4)を示す。 二つの完全$r$部グラフの部の大きさの多重集合が等しいとする。大きさの等しい部どうしを対応させ、対応する部の間の全単射を各部で一つ選ぶ。それらを合わせると頂点集合の間の全単射が得られる。この全単射は「相異なる部に属する」という関係を両向きに保つので、辺を辺へ、非辺を非辺へ写し、グラフの同型である。$(1)$より$T(n,r)$の部の大きさの多重集合は$n$と$r$だけで定まるから、$T(n,r)$は同型を除いて一意に定まる。▨

証明.$\mathcal P$を$V$の二元部分集合の全体とすると、§D2.2 命題 3.1より$\lvert\mathcal P\rvert=\binom n2$である。$\mathcal P$を、両方の頂点が同じ部に属する対の全体$\mathcal P_0$と、相異なる部に属する対の全体$\mathcal P_1$へ分ける。二つは互いに素であり合併は$\mathcal P$であるから、§D2.2 定理 2.1より$\lvert\mathcal P_0\rvert+\lvert\mathcal P_1\rvert=\binom n2$である。

$\mathcal P_0$は、各$i$について$V_i$の二元部分集合の全体を集めたものであり、相異なる$i$に対するこれらは互いに素である。ゆえに§D2.2 定理 2.1と§D2.2 命題 3.1より$\lvert\mathcal P_0\rvert=\sum_{i=1}^{r}\binom{n_i}{2}$である。したがって$\lvert\mathcal P_1\rvert=\binom n2-\sum_{i=1}^{r}\binom{n_i}{2}.$

各$V_i$は独立集合であるから、$E$の元は同じ部に属する二頂点の対ではない。ゆえに$E\subseteq\mathcal P_1$であり$\lvert E\rvert\le\lvert\mathcal P_1\rvert$である。等号が成立することは$E=\mathcal P_1$と同値であり、これは相異なる部に属する任意の二頂点が隣接することにほかならない。▨

証明. 和が$n$である非負整数の組は有限個であるから、$F(n_1,\dots,n_r)=\sum_{i=1}^{r}\binom{n_i}{2}$を最小にする組が存在する。そのような組を一つ取り、$(n_1,\dots,n_r)$と書く。

この組はすべての$i,j$について$\lvert n_i-n_j\rvert\le1$を満たす。実際、$n_i\ge n_j+2$を満たす添字の対が存在するとし、$n_i$を$n_i-1$へ、$n_j$を$n_j+1$へ置き換えた組を考える。和は変わらず、$F$の値の変化は$\left[\binom{n_i-1}{2}-\binom{n_i}{2}\right]+\left[\binom{n_j+1}{2}-\binom{n_j}{2}\right]=-(n_i-1)+n_j=n_j-n_i+1\le-1$である。ここで$\binom{a}{2}-\binom{a-1}{2}=a-1$を用いた。$F$の値が真に小さくなるので、最小性に反する。

ゆえに最小値を与える組は定義 2.2の条件を満たす部の大きさであり、命題 2.3 (1)より$(m_1,\dots,m_r)$の並べ替えである。並べ替えは$F$の値を変えないから、$(m_1,\dots,m_r)$の並べ替えはすべて最小値を与える。

逆に、$(n_1,\dots,n_r)$が$(m_1,\dots,m_r)$の並べ替えでないとする。このとき命題 2.3 (1)より、$n_i\ge n_j+2$を満たす添字の対が存在する。上の置き換えによって$F$の値が真に小さい組が得られるから、$(n_1,\dots,n_r)$は最小値を与えず、$F(n_1,\dots,n_r)>\sum_i\binom{m_i}{2}$である。▨

証明.主張 (1)を示す。$T(n,r)$は相異なる部に属する二頂点をすべて結んだグラフであるから、命題 3.1の等号成立条件を満たす。ゆえに主張の等式が成り立つ。

主張 (2)を示す。$n>r$のとき$q=\lfloor n/r\rfloor\ge1$であるから、すべての$i$について$m_i\ge1$である。組$(m_1-1,\dots,m_r-1)$は非負整数の組であり、その和は$n-r\ge1$、各成分の差は$(m_1,\dots,m_r)$の差と同じであるから$1$以下である。命題 2.3 (1)より、これは$T(n-r,r)$の部の大きさの組である。ゆえに$(1)$より$\lvert E(T(n-r,r))\rvert=\binom{n-r}{2}-\sum_{i=1}^{r}\binom{m_i-1}{2}$である。差を取ると、$\binom{m_i}{2}-\binom{m_i-1}{2}=m_i-1$と$\sum_i(m_i-1)=n-r$より$\lvert E(T(n,r))\rvert-\lvert E(T(n-r,r))\rvert=\binom n2-\binom{n-r}{2}-\sum_{i=1}^{r}(m_i-1)=\binom n2-\binom{n-r}{2}-(n-r).$ここで$\binom n2-\binom{n-r}{2}=\frac{n(n-1)-(n-r)(n-r-1)}{2}=\frac{2nr-r^{2}-r}{2}=nr-\frac{r(r+1)}{2}$であるから$\lvert E(T(n,r))\rvert-\lvert E(T(n-r,r))\rvert=nr-\frac{r(r+1)}{2}-n+r=n(r-1)-\frac{r(r-1)}{2}$となる。一方$\binom r2+(r-1)(n-r)=\frac{r(r-1)}{2}+(r-1)n-r(r-1)=n(r-1)-\frac{r(r-1)}{2}$であるから、二つは等しい。▨

証明.$G$が完全グラフである場合、$V$自身がクリークであり、$K_{r+1}$を含まないことから$n\le r$である。仮定$n\ge r$とあわせて$n=r$であり、$V$が$r$元クリークである。

$G$が完全グラフでない場合、$u\ne v$かつ$uv\notin E$を満たす$u,v\in V$が存在する。仮定より$G+uv$は$(r+1)$元クリーク$S$をもつ。$G$は$K_{r+1}$を含まないから、$S$の二頂点の対のうち少なくとも一つは$G$の辺ではない。$G+uv$で新たに加わった辺は$uv$だけであるから、その対は$\{u,v\}$であり、$u,v\in S$である。

$S'=S\setminus\{v\}$と置くと$\lvert S'\rvert=r$である。$S'$の相異なる二頂点の対は$\{u,v\}$とは異なるから、$G+uv$の辺であることと$G$の辺であることが同値である。$S$がクリークであることより、$S'$のすべての対は$G+uv$の辺であり、したがって$G$の辺である。ゆえに$S'$は$G$の$r$元クリークである。▨

証明.$\lvert B\rvert=n-r\ge1$であるから$B\ne\varnothing$であり、$G[B]$は$n-r$頂点のグラフである。

主張 (1)を示す。$G$の各辺は、両端点が$A$に属するか、両端点が$B$に属するか、一方の端点が$A$で他方が$B$に属するかのいずれかであり、$V=A\sqcup B$であるから三つの場合は互いに排反である。ゆえに§D2.2 定理 2.1より$\lvert E\rvert=\lvert E[A]\rvert+\lvert E(A,B)\rvert+\lvert E[B]\rvert$である。$A$はクリークであるから$E[A]$は$A$の二元部分集合の全体に等しく、§D2.2 命題 3.1より$\lvert E[A]\rvert=\binom r2$である。

主張 (2)を示す。 和による表示は系 2.1による。$v\in B$が$A$のすべての頂点と隣接するとすると、$A$がクリークであることから$A\cup\{v\}$は$(r+1)$元クリークとなり、$G$が$K_{r+1}$を部分グラフとして含まないことに反する。ゆえに各項は$r-1$以下であり、項の個数は$\lvert B\rvert=n-r$であるから$\lvert E(A,B)\rvert\le(r-1)(n-r)$である。各項が$r-1$以下である$n-r$個の和が$(r-1)(n-r)$に等しいことと、各項が$r-1$に等しいことは同値である。

主張 (3)を示す。$G[B]$のクリークは$G$のクリークでもあるから、$G$が$(r+1)$元クリークをもたないことより$G[B]$も$(r+1)$元クリークをもたない。▨

証明.$n$についての累積帰納法（§D2.1 命題 1.2）で不等式を示す。

$n\le r$の場合.命題 2.3 (3)より$T(n,r)\cong K_n$であり、$\lvert E(T(n,r))\rvert=\binom n2$である。$E(G)$は$V$の二元部分集合の集合の部分集合であるから$\lvert E(G)\rvert\le\binom n2$である。

$n>r$の場合.$V$上の有限単純無向グラフ$H$であって$E(G)\subseteq E(H)$かつ$H$が$K_{r+1}$を部分グラフとして含まないものの全体を考える。$V$上のグラフは有限個であり、$G$自身がこの条件を満たすから、この全体は空でない有限集合である。ゆえに、そのうち辺数が最大のものを一つ取ることができる。これを$G^{+}$とする。$G^{+}$の非辺$uv$を加えて得られるグラフは、辺数が$G^{+}$より大きく$E(G)$を含むから、$G^{+}$の取り方より$K_{r+1}$を部分グラフとして含む。したがって$G^{+}$は補題 4.1の仮定を満たす。$n>r$より$n\ge r$であるから、$G^{+}$は$r$元クリーク$A$をもつ。

$B=V\setminus A$と置くと$\lvert B\rvert=n-r\ge1$である。補題 4.2 (1)と補題 4.2 (2)より$\lvert E(G^{+})\rvert=\binom r2+\lvert E(A,B)\rvert+\lvert E[B]\rvert\le\binom r2+(r-1)(n-r)+\lvert E[B]\rvert$である。ここで記号$E[B]$と$E(A,B)$は定義 1.1と系 2.1のものであり、いずれも$G^{+}$について取る。

補題 4.2 (3)より、$G^{+}[B]$は$K_{r+1}$を部分グラフとして含まない$n-r$頂点のグラフである。$1\le n-r<n$であるから、帰納法の仮定より$\lvert E[B]\rvert\le\lvert E(T(n-r,r))\rvert$である。

以上を合わせ、命題 3.3 (2)を用いると$\lvert E(G)\rvert\le\lvert E(G^{+})\rvert\le\binom r2+(r-1)(n-r)+\lvert E(T(n-r,r))\rvert=\lvert E(T(n,r))\rvert$を得る。

最後に、命題 2.3 (2)より$T(n,r)$は$K_{r+1}$を部分グラフとして含まないから、上界は達成される。ゆえに$\operatorname{ex}(n;K_{r+1})=\lvert E(T(n,r))\rvert$である。▨

証明. 十分性.$G\cong T(n,r)$ならば辺数は等しい。

必要性.$\lvert E(G)\rvert=\lvert E(T(n,r))\rvert$とする。

$n\le r$の場合.命題 2.3 (3)より$\lvert E(G)\rvert=\binom n2$であり、$E(G)$は$V$の二元部分集合の全体に含まれて同じ濃度をもつから、$E(G)$はその全体に等しい。ゆえに$G\cong K_n\cong T(n,r)$である。

$n>r$の場合. まず$G$が辺極大であることを示す。定理 4.3の証明と同じく、$G$を含み$K_{r+1}$を部分グラフとして含まない$V$上のグラフのうち辺数が最大のものを$G^{+}$とする。定理 4.3より$\lvert E(G^{+})\rvert\le\lvert E(T(n,r))\rvert=\lvert E(G)\rvert\le\lvert E(G^{+})\rvert$であるから$E(G)=E(G^{+})$であり、$G$自身が補題 4.1の仮定を満たす。ゆえに$G$は$r$元クリーク$A=\{a_1,\dots,a_r\}$をもつ。

$B=V\setminus A$と置くと$\lvert B\rvert=n-r\ge1$である。補題 4.2 (1)と補題 4.2 (2)、補題 4.2 (3)と定理 4.3、および命題 3.3 (2)を順に用いると$\lvert E(G)\rvert=\binom r2+\lvert E(A,B)\rvert+\lvert E[B]\rvert\le\binom r2+(r-1)(n-r)+\lvert E(T(n-r,r))\rvert=\lvert E(T(n,r))\rvert=\lvert E(G)\rvert$となるから、途中の二つの不等号はいずれも等号である。とくに$\lvert E(A,B)\rvert=(r-1)(n-r)$であり、補題 4.2 (2)の等号成立条件より、すべての$v\in B$について$\lvert N_G(v)\cap A\rvert=r-1$である。

$\lvert A\rvert=r$であるから、各$v\in B$に対し$va\notin E$を満たす$a\in A$がただ一つ存在する。これを$f(v)$と書き、$B_i=\{v\in B:\ f(v)=a_i\},\qquad V_i=B_i\cup\{a_i\}\qquad(i=1,\dots,r)$と置く。$B=B_1\sqcup\dots\sqcup B_r$かつ$A=\{a_1,\dots,a_r\}$であるから、$V=V_1\sqcup\dots\sqcup V_r$は$V$の分割である。

各$V_i$が独立集合であることを示す。まず、$v\in B_i$に対し$f(v)=a_i$であるから$va_i\notin E$である。次に、相異なる$u,v\in B_i$が$uv\in E$を満たすと仮定する。$S=\{u,v\}\cup(A\setminus\{a_i\})$と置くと$\lvert S\rvert=2+(r-1)=r+1$である。$S$の相異なる二頂点の対を調べる。対$\{u,v\}$は仮定より辺である。$j\ne i$のとき、$f(u)=a_i$より$u$は$A\setminus\{a_i\}$のすべての頂点と隣接するから、対$\{u,a_j\}$は辺である。同じ理由で対$\{v,a_j\}$も辺である。$A$はクリークであるから、$j\ne k$に対する対$\{a_j,a_k\}$も辺である。ゆえに$S$は$(r+1)$元クリークとなり、$G$が$K_{r+1}$を部分グラフとして含まないことに反する。したがって$B_i$は独立集合であり、$V_i$も独立集合である。

$n_i=\lvert V_i\rvert$と置く。命題 3.1と命題 3.2、および命題 3.3 (1)より$\lvert E(G)\rvert\le\binom n2-\sum_{i=1}^{r}\binom{n_i}{2}\le\binom n2-\sum_{i=1}^{r}\binom{m_i}{2}=\lvert E(T(n,r))\rvert=\lvert E(G)\rvert$であるから、二つの不等号はいずれも等号である。ここで$m_1,\dots,m_r$は$T(n,r)$の部の大きさである。

第一の等号と命題 3.1の等号成立条件より、$G$は分割$V_1,\dots,V_r$に関する完全$r$部グラフである。第二の等号と命題 3.2の等号成立条件より、$(n_1,\dots,n_r)$は$(m_1,\dots,m_r)$の並べ替えである。$G$と$T(n,r)$はいずれも完全$r$部グラフであって部の大きさの多重集合が等しいから、命題 2.3 (4)より$G\cong T(n,r)$である。▨