まずは友好定理の主張について確認しましょう。

主張

グラフ\(\,G\,\)を「あるグループ」，\(\,G\,\)の点を「グループ内の人たち」，\(\,G\,\)の辺を「知り合いである状態」と考えれば，
イメージは次のようになります。

このように全ての人と知り合いであるような人，
言わば「顔の広い政治家」がいるので，友好定理の名前が付けられているわけですね。

この記事ではこのようなイメージに基づいて解説を行うので，以下のように用語を定義します。

友好グラフ(friendship graph)

ここで友好条件を満たすグラフ\(\,G\,\)がどのようなグラフなのか考えましょう。

友好定理により\(\,G\,\)には政治家\(\,p\,\)が存在しています。

そこで\(\,G\,\)の点の数を\(\,n \in \mathbb{N} \,\)とおくと\(\,p\,\)と知人である点は
\(\,v_1,v_2,\ldots,v_{n-1}\,\)と書けます。

友好条件より点\(\,p\,\)と点\(\,v_1\,\)と知人である点がただ一つ存在します。

ラベルを付け変えることによって，その点を\(\,v_2\,\)と改めて書きましょう(下図)。

このとき\(\,G\,\)の性質から点\(\,v_1,v_2\,\)はもうこれ以上辺を持たないことに注意してください。

なぜならこれ以上辺を持ってしまうと，点\(\,p\,\)との共通の知人が二人以上存在することになってしまうからです。

そこで次に点\(\,v_3\,\)について考えましょう。

同様に考えると\(\,G\,\)は下図のように書けます。

これを繰り返していくと，\(\,2\,\)通りの場合に分けられます。

\([1]\) \(\,n\,\)が偶数のとき

このとき点\(\,v_{n-1}\,\)と点\(\,p\,\)との共通の知人について考えると，どう頑張っても友好条件を満たせないことが分かります。

よってこの場合はあり得ません。

\([2]\) \(\,n\,\)が奇数のとき

友好条件から，もうこれ以上辺を追加することができません。

また逆にこのグラフが友好条件をきちんと満たしていることも簡単に確かめられます。

つまり上図のような形のグラフしか友好定理の性質を満たすものがないことが分かります。

そこでこのグラフを友好グラフと呼びましょう。

点の数\(\,n\,\)が少ない順に友好グラフを書くと，次のようになります。

この章では友好定理の証明を確認していきます。

グラフ理論と線形代数学が交差する面白い証明です。

グラフ理論編

まずは簡単に分かることとして，
友好条件を満たすグラフ\(\,G\,\)は長さ\(\,4\,\)のサイクルを持たないことを確認しましょう。

長さ\(\,4\,\)のサイクルを持つということは下図のような状態が存在することになります。

このとき点\(\,u,v\,\)には共通の知人が二人以上いることになり，友好条件に反します。

したがって\(\,G\,\)は長さ\(\,4\,\)のサイクルを持ちません。

この事実は証明内で度々用いるので，改めて\(\,C_4\,\)条件と呼ぶことにします。

背理法により友好定理を示すため，まず下の補題を証明します。

[証明]\(\quad\)適当な点\(\,u \in G\,\)を固定しましょう。

まず\(\,u\,\)と知り合いでない任意の点\(\,v\,\)について\(\,u,v\,\)の次数が等しいことを示しましょう。

※政治家が存在しないという仮定から\(\,v\,\)は少なくとも一つ存在します。

点\(\,u\,\)の次数を\(\,k \in \mathbb{N}\cup\{0\}\,\)，すなわち\(\,d(u)=k\,\)と書きましょう。

\(\,k=0\,\)のときは友好条件より，そのグラフは点\(\,u\,\)のみとなり，これは自分しかいないグループで\(\,u\,\)自身が政治家となることを意味しています。

それは仮定に矛盾するので\(\,k\in \mathbb{N}\)とできます。

また\(\,k=1\,\)のときは，\(\,u\,\)がその知人と共通の知人を作ってしまうと\(\,u\,\)の次数が上がるため，友好条件を満たすことはありません。

そのため\(\,k\geq 2\,\)とできます。

\(\,u\,\)の知人たちは\(\,w_1,\ldots,w_k \,\)と書けて，
点\(\,u,v\,\)の友好条件から，その中に\(\,u,v\,\)の共通の知人が存在します。

ラベルを取り換えることで，その知人を\(\,w_2\,\)としましょう。

また同様に点\(\,u,w_2\,\)の友好条件から，
\(\,w_1,w_3,\ldots,w_k \,\)の中にその共通の知人が存在します。

再びラベルを取り換えることで，その知人を\(\,w_1\,\)としましょう。

また\(\,w_i\>\;(2\leq i \leq k)\,\)と\(\,v\,\)の友好条件から，その共通の知人\(\,z_i\,\)が存在することが分かります。

このとき各\(\,z_i\,\)は異なります。なぜならもし同じ点\(\,z_i,z_j\,\)があると\(\,C_4\,\)条件と矛盾するからです(下図)。

よってこの時点で\(\,v\,\)には\(w_2,z_2,\ldots,z_k\)の\(\,k\,\)個の点と知り合いなので，
\(\,d(v) \geq k = d(u)\,\)となることが分かります。

議論は対称的なので\(\,d(u) \geq d(v)\,\)も示され，\(\,d(v)=d(u)\,\)となることが分かりました。

つまり\(\,u\,\)と，\(\,u\,\)と知人でない点の次数は等しいことが分かりました。

次に\(u\)と知人である点\(\,w_1,\ldots,w_k \,\)について考えましょう。

この中で\(w_2\)以外の点は\(\,v\,\)と知人ではありません。

なぜなら下図のようになり\(C_4\)条件と矛盾するからです。

そのため先ほどと同様の議論を\(\,v,w_i\;\>(i\not=2)\,\)に適用すれば，
\(\,w_2\,\)以外の点は\(\,v\,\)と次数が等しいです(すなわち\(\,u\,\)とも次数が等しい)。

さらに仮定より\(\,w_2\,\)も政治家でないので，グループ内に知人でない点が存在します。

再び同様の議論で，この点と\(w_2\)の次数は等しい(すなわち\(\,u\,\)とも次数が等しい)です。

したがって\(\,G\,\)は正則グラフであることが示されました。

また\(\,G\,\)の\(\,u\,\)以外の点は\(\,u\,\)との友好条件より
\(\,w_1,\ldots,w_k \,\)のうちのたった一人と知人になっています。

そのため\(\,w_1,\ldots,w_k \,\)の次数の合計\(\,k^2\,\)について

\(\,k^2=(G\,\)の点の数\()\,+\,\)\(\,(u\,\)のカウント数\()\,-1\,\)

となっています。

\(\,u\,\)は\(\,k\,\)回数えられるので，この式から

点の数は\(\,k^2-k+1 \;\>(k\in \mathbb{N},k \geq 2)\)となることが分かります。

以上より補題は示されました。

線形代数学編

前節で得られた補題と線形代数学を合わせて，友好定理の証明を完成させましょう。

補題のグラフ\(\,G\,\)についての隣接行列を\(\,A\,\)とおきましょう。

このとき\(\,A^2\,\)の表式を求めていきます。

※なぜそうするのかは，\(A^2\)は長さ\(\,2\,\)の歩道の本数の情報を持っているという性質があることによります。隣接行列の記事をご覧ください。

ここは\(\,A\,\)が\(\,(k^2-k+1)\)次実対称行列であることに注意しながら読んでください。

補題より\(\,G\,\)の点の次数は\(\,k\,\)であることから，\(\,A\,\)の各行・列にはちょうど\(\,k\,\)個の\(\,1\,\)があり，それ以外は\(\,0\,\)です。

よって\(A^2\)の対角成分は\(\,1\times k =k\,\)となることが分かります。

また友好条件より異なる\(\,2\,\)行について，その成分が共に\(\,1\,\)となる列はたった\(\,1\,\)つであることが分かります。

そのため\(A^2\)の対角でない成分は\(\,1\times 1=1\,\)になることが分かります。

つまり

\(A^2 = \left(\begin{array}{cccc}k & 1 & \ldots & 1 \\ 1 & k & \ldots & 1 \\\vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \ldots & k \end{array}\right)\)

です。

補遺\([1]\)より\(\,A^2\,\)の固有値は

\(\,k^2\,\)(重複度\(\,1\,\))，\(\,k-1\,\)(重複度\(\,(k^2-k+1)-1\,\))となります。

よって\(\,A\,\)の固有値はその根号を取った

\(\,\pm\sqrt{k-1},\pm{k}\,\)のどれかとなります。

その重複度について考えていきましょう。

\(\,k^2\,\)の重複度が\(\,1\,\)だったので，\(+k,-k\,\)の重複度の和は\(\,1\,\)となります。

ここで\(\,A\,\)の各行にはちょうど\(\,k\,\)個の\(\,1\,\)があったことより，

\(\,A\mathbf{1}=k\mathbf{1}\,\)が成り立ちます。

※\(\,\mathbf{1}\,\)は全ての成分が\(\,1\,\)である列ベクトルです。

そのため\(\,A\,\)は\(\,-k\,\)を固有値として持たず，固有値\(\,k\,\)(重複度\(\,1\,\))を持つことが分かります。

ここで\(+\sqrt{k-1},-\sqrt{k-1}\,\)の重複度をそれぞれ\(\,r,s \in \mathbb{N}\cup\{0\}\)と置くと

\(\,\mathrm{Tr}(A)=0\,\)は明らかなので，

\(\,k+r\sqrt{k-1}-s\sqrt{k-1}=0\,\)が成り立ちます。

\(\,s=r\,\)とすると\(\,k=0\,\)となってしまい，矛盾するので\(\,s\not=r\,\)です。

そのため式変形により

\(\sqrt{k-1}=\dfrac{k}{s-r}\,\)となります。

つまり\(\,\sqrt{k-1}\,\)は有理数となるので，

補遺\([2]\)より\(\,h=\sqrt{k-1}\in \mathbb{N}\,\)となります。

\(h^2=k-1\,\)より\(\,h\,\)は\(\,k-1\,\)の約数です。

また先ほどの式より\(\,h(s-r)=k\,\)なので，\(\,k\,\)の約数でもあります。

しかし\(\,k-1,k\,\)は隣り合う自然数なので，正の公約数は\(\,1\,\)のみです。

つまり\(\,h=1\Leftrightarrow k=2\,\)となります。

ここまでの情報をまとめると，

友好条件を満たすのに，政治家が存在しないグラフ\(\,G\,\)は
点の数が\(\,2^2-2+1=3\,\)の\(2\text{-}\)正則グラフとなるということです。

友好条件を満たし，点の数が\(\,3\,\)の\(2\text{-}\)正則グラフは下の三角形のみとなりますが，

これは政治家が存在しています(むしろ全ての点が政治家です)。

したがって友好条件を満たすのに，政治家が存在しないグラフ\(\,G\,\)は存在しないことが分かりました。

したがって題意は示されました。\(\quad\square\)

今回の記事では友好定理を解説いたしました。

証明の中でグラフ理論と線形代数学が合わさっていて，非常に面白かったですね。

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

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

ここでは線形代数学編で用いた，次の\(\,2\,\)つのことを証明していきましょう。

\([1]\)について，\(\,A^2\,\)の特性方程式\(\,|A^2-xI|=0\,\)を解けばよいですね。

\(\,A^2\,\)は\(\,(k^2-k+1)\)次行列のため，記述の手間を省くため\(\,n=k^2-k+1\,\)と置くことにすると

となります。

したがって\([1]\)は示されました。

ちなみに各手順の詳細は次のようになります。

\((1)\to(2)\) 第\(\,1\,\)列に，他の列の成分をすべて足す。

\((2)\to(3)\) 第\(\,1\,\)列を\(\,(k-x+n-1)\,\)でくくる。

\((3)\to(4)\) 第\(\,1\,\)列の成分で，他の列を引く。

\((4)\to(5)\) 対角成分を取っていく。

続いて\([2]\)についてです。背理法により証明していきます。

\(\sqrt{m}\,\)は正かつ，仮定より有理数なので

\(n_0\sqrt{m}\in \mathbb{N}\,\)となるような\(\,n_0\in \mathbb{N}\,\)をとることができます。

その中で最小なものが\(\,n_0\,\)であるとしましょう。

\(\sqrt{m}\,\)が自然数でないとすると，

\(\,0\lt \sqrt{m}-l \lt 1\,\)が成り立つような\(\,l\in\mathbb{N}\cup\{0\}\,\)が存在します。

※ガウス記号を用いて\(\,l=[\,\sqrt{m}\,]\,\)としていることと同じです。

このとき\(\,n_1=n_0(\sqrt{m}-l)\,\)とおきましょう。

\(\,\sqrt{m}-l\gt 0\,\)より\(\,n_1\gt 0\,\)で

\(n_0\sqrt{m}\in\mathbb{N}\,\)より\(\,n_1=n_0\sqrt{m}-n_{0}l\in \mathbb{Z}\,\)です。

つまり\(\,n_1\in \mathbb{N}\,\)です。

また\(\,n_1\sqrt{m}=n_0(\sqrt{m}-l)\sqrt{m}=n_{0}m-l(n_{0}\sqrt{m})\in\mathbb{N}\,\)であり，

さらに\(\,\sqrt{m}-l\lt 1\,\)より\(\,n_1\lt n_0\,\)です。

これは\(\,n_0\,\)の最小性に矛盾します。

したがって背理法により\([2]\)は示されました。\(\quad\square\)

• \([1]\) Martin Aigner,Günter M. Ziegler.”Proofs from THE BOOK”.Sixth Edition.Springer.2018出版.p.307-309.
• \([2]\) 惠羅博,土屋守正.”シリーズ／情報科学の数学　増補改訂版　グラフ理論”.増補改訂版.産業図書.2010出版.p24-26.