ここでは以下のトゥラングラフの最大性を示すことが目的になります。

関係\(\,\sim\,\)の定義

まずは\(\,n\,\)点からなり\(\,p\text{-}\)クリークを持たないグラフの中で，
辺の数が最大となるグラフの形をじわじわと特定していきましょう。

つまり次の補題\([1]\)を示します。

完全\(\,k\,\)部グラフは点集合を\(\,k\,\)個のグループに分割し，異なるグループに属する点は辺で結ぶことで作られます。

実はこの分割は，同値関係による分割として捉えることができます。

任意のグラフ\(\,G\,\)の点\(\,u,v\in V(G)\,\)に対し次のように定義される関係\(\,\sim\,\)を考えましょう。

\(u\sim v\,\Leftrightarrow\, uv\not\in E(G)\)

この関係を使えば完全\(\,k\,\)部グラフの定義は以下のように書き換えられます。

\(\Leftarrow\,\)は，同値関係\(\,\sim\,\)によって\(\,G\,\)の点集合を同値類に分割でき，その分割によって\(\,G\,\)が完全\(\,k\,\)部グラフとなることから簡単に分かります。

\(\Rightarrow\,\)について考えましょう。

\(\sim\,\)は定義より反射律，対称律を満たすのは明らかですので，推移律のみを考えれば良いですね。

つまり任意の\(\,u,v,w\in G\,\)について
\(\,u\sim v,v\sim w\Rightarrow u\sim w\,\)が分かれば良いですね。

完全\(\,k\,\)部グラフの分割について

\(\,u\sim v\,\)より\(\,u,v\,\)は同じグループに属し，

\(\,v\sim w\,\)より\(\,v,w\,\)も同じグループに属します。

よって\(\,u,w\,\)も同じグループに属するので\(\,u\sim w\,\)となり，\(\Rightarrow\,\)が示されました。

この同値性を使えば補題\([1]\)は次の補題\([1]’\)と同値です。

ここで\(n\,\)点からなり\(\,p\text{-}\)クリークを持たないグラフの中で，

辺の数が最大となるようなグラフを\(\,M\,\)とおきましょう。

すると先程も述べたように反射律と対称律明らかなので，

\(\,u,v,w \in M\,\)について
推移律\(\,u\sim v,v\sim w\Rightarrow u\sim w\,\)を示せば良いですね。

現在の状況を整理すると\(\,u\sim v,v\sim w\)より下図のようになっています。

この図で？の部分に辺がないことを示していくということですね。

次節から，この\(\,u\sim w\,\)を\(\,2\,\)つのcaseに分けて考えていきましょう。

case1: \(\,d(v)\lt d(u)\,\)または\(\,d(v)\lt d(w)\,\)

case1はそもそも起こり得ないことを，\(\,M\,\)の最大性との矛盾により証明します。

一般性を失わないので，\(\,d(v)\lt d(u)\,\)の条件の方が成り立つとして考えます。

ここで点\(\,u\,\)を複製することで，新たに点\(\,u’\,\)を作った後，点\(\,v\,\)を取り除きます(下図)。

ただし「点\(\,u\,\)を複製する」とは\(\,u\,\)と隣接状況が同じ新たな\(\,1\,\)点を作ることです。

この変化後のグラフを\(\,M’\,\)とおくと，\(\,M’\,\)は\(\,n\,\)点からなり\(\,p\text{-}\)クリークを持ちません。

もし先程の操作によって\(\,p\text{-}\,\)クリークができたとすると，

そのクリーク内には新たにできた点\(\,u’\,\)が含まれていることになります。

しかし点\(\,u’\,\)と点\(\,u\,\)の隣接状況は同じなので，

このことはもともと\(\,M\,\)内に点\(\,u\,\)を含む\(\,p\text{-}\)クリークがあったことを意味し，矛盾してしまうからです。

また\(\,M’\,\)の辺の数\(\,|E(M’)|\,\)について考えれば，\(\,d(v)\lt d(u)\,\)より

\(|E(M’)|=|E(M)|+d(u)-d(v)\gt |E(M)|\,\)

となります。

このことは\(\,M\,\)の最大性に矛盾するので，

このcase1はそもそも起こり得ません。

case2: \(\,d(v)\geq d(u)\,\)かつ\(\,d(v)\geq d(w)\,\)

前節でcase1はそもそも起こりえないことが分かったので，

case2で\(u\sim w\)となることを示せば良いですね。

そのために\(\,u \not\sim w\,\)と仮定して背理法により示していきます(下図の状況を仮定)。

今度は点\(\,v\,\)を\(\,2\,\)回複製して，\(\,2\,\)点\(\,v’,v”\,\)を作った後，\(\,2\,\)点\(\,u,w\,\)を取り除きます。

もう一度この操作後のグラフを\(\,M’\,\)とおくと，\(\,M’\,\)は\(\,n\,\)点からなり，

case1と同様の考え方で\(\,M’\,\)内に\(\,p\text{-}\)クリークはできないことが分かります。

\(\,d(v)\geq d(u)\,\)かつ\(\,d(v)\geq d(w)\,\)より\(\,M’\,\)の辺の数\(\,|E(M’)|\,\)は以下のようになります。

\(|E(M’)|=|E(M)|+2d(v)-(d(u)+d(w)-1)\gt |E(M)|\,\)

※\(\,1\,\)が出てきたところに\(\,u \not\sim w\,\)の仮定が使われています。

よって\(\,M’\,\)の最大性に矛盾するので，背理法により\(\,u\sim w\,\)であることが分かります。

以上のcase1,2から\(\,\sim\,\)が同値関係であることが分かったので，補題\([1]\)は示されました。

トゥラングラフのみに限ることの帰結

前節で上の補題\([1]\)を示しました。

そのため残りの

を示していきます。

補題\([1]\)の証明のときと同様に，\(n\,\)点からなり\(\,p\text{-}\)クリークを持たない完全\(\,k\,\)部グラフの中で，

辺の数が最大となるようなグラフを\(\,M\,\)とおきましょう。

\(k\gt p-1\,\)とすると，完全\(\,k\,\)部グラフの定義から\(\,p\text{-}\)クリークを持ってしまうので\(\,k\leq p-1\,\)となります。

このとき点集合の分割\(\,V_1,V_2,\ldots,V_{p-1}\,\)に空集合(\(\,n_i=0\,\))を認めることで，

\(M=\,K_{n_1,n_2,\ldots,n_{p-1}}\,\)とおいても構いません。

背理法により示すためトゥラングラフの性質

「任意の自然数\(\,1\leq i,j\leq p-1\,\)に対して\(\,|n_i-n_j|\leq 1\,\)となる」

を満たさないと仮定しましょう。

つまり「ある自然数\(\,1\leq i,j\leq p-1\,\)に対して\(\,|n_i-n_j|\gt 1\,\)となる」ということです。

一般性を失わないので\(\,n_1-n_2\gt 1\,\)としても構いません。

ここで\(\,V_1\,\)から\(\,V_2\,\)に\(\,1\,\)点だけ移動させた，

完全\(\,(p-1)\,\)部グラフ\(K_{(n_1-1),(n_2+1),\ldots,n_{p-1}}\)を考えましょう。

一般にグラフ\(\,K_{n_1,n_2,\ldots,n_{p-1}}\,\)の辺の数は，

\(\displaystyle |E(K_{n_1,n_2,\ldots,n_{p-1}})|=\sum_{i\lt j}^{p-1} n_in_j\)

となることが分かります(直感的に明らかでない方は握手補題を使うと良いでしょう)。

そのため\(\,n_1-n_2\gt 1\,\)より，次の式変形が成り立ちます。

つまり\(\,|E(K_{(n_1-1),(n_2+1),\ldots,n_{p-1}})| \gt |E(M)|\)となることが示されました。

これは\(\,M\,\)の最大性に矛盾するので，題意は示されました。\(\quad\square\)

今回の記事ではトゥラングラフを解説いたしました。

トゥラングラフの最大性を示す証明は他にもあるので，

気になった方は参考図書\([1]\)のSecond proof.をご覧になると良いでしょう。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

• \([1]\) Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.285-289.