三角形・四角形を含まないグラフ(極値グラフ理論)

0. 概要

グラフ理論の中に「極値グラフ理論 (extremal graph theory)」と呼ばれる分野があります. 極値グラフ理論では, 「与えられた性質$\mathcal{P}$を満たすグラフのうち, 最大辺数を求める」ことを考えます. 極値グラフ理論で最も有名な結果はおそらくTuranの定理でしょう. これは, 性質$\mathcal{P}$を「サイズ$r$の完全グラフ$K_r$を含まない」としたとき, 辺数が最大のグラフは$r-1$部完全グラフであるという結果です.

気持ちとしては, 「どれほどの辺数を持てばグラフが性質$\mathcal{P}$を満たすことを保証できるか」という問題について考えるのが極値グラフ理論です.

1. Triangle-free グラフ

「三角形($=K_3$)を含まない」という性質を満たすグラフのうち最大辺数を持つグラフを考えます. (このようなグラフをtriangle-freeグラフといいます). こちらのページで紹介されているように(またはTuranの定理の帰結として), 完全二部グラフを考えると, 三角形を含まないような頂点数$n$のグラフが持ちうる辺数はおおよそ, 高々$\frac{n^2}{4}=O(n^2)$となります.

2. Triangle & Square-free グラフ

では, 「三角形・四角形を含まない」という性質を満たすグラフの最大辺数について考えます. 結論から言うとこのような性質を持つ頂点数$n$のグラフの辺数は高々$O(n^{1.5})$となることが示せます. 「奇数長の閉路を含まない」という制約を考えても完全二部グラフがとれるので, 辺数が$O(n^2)$になります. しかし四角形の制約を付け加えるだけでオーダーが劇的に下がる, という点が面白い点です. この結果はとても簡単に証明できるので, 紹介します.

定理. 三角形及び四角形を含まない$n$頂点のグラフ$G$の辺数は高々 $\frac{n\sqrt{n-1}}{2}$ である.

証明.
$G=(V,E)$を三角形・四角形を含まない$n$頂点のグラフとします. このグラフが含む長さ2のパスの本数を二通りの方法で数えます:

図のように, 頂点$v$を一つ選んだときに$v$を真ん中の頂点として持つような長さ2のパスを考えます. そのようなパスの個数は$v$に対して$i,j$の選び方の総数に等しいので, $\binom{d_v}{2}=\frac{d_v(d_v-1)}{2}$となります. ここで$d_v$は頂点$v$の次数です.
従って, 長さ2のパスの総数は



となります.


一方, $G$が四角形を含まないため, 隣接していない二頂点$i,j$を選択したときに, $i,j$を端点として持つような長さ2のパスは高々1本となります (下図). 従って, 長さ2のパスの本数は非隣接的な二頂点の選び方の総数, 即ち$\binom{n}{2}-|E|$で上から抑えることが出来ます.

非隣接頂点対$i,j$に対して, $i$と$j$の両方と隣接している頂点は高々一つである.

従って



よって,

                    ...(1)

となります.


次にコーシーシュワルツの不等式を用います. コーシーシュワルツの不等式は

$\left(\sum_v x_v y_v\right)^2 \leq \left(\sum_v x_v^2\right)\left(\sum_v y_v^2\right)$

ですが, これに$x_v=d_v$, $y_v=1$を代入すると

$4|E|^2 = \left(\sum_v d_v\right)^2 \leq n\sum_v d_v^2$                    ...(2)


(1)(2)より,

$\frac{4|E|^2}{n}\leq \sum_v d_v^2 \leq n(n-1)$

従って,

$|E| \leq \frac{\sqrt{n^3-n}}{2} = \frac{n\sqrt{n-1}}{2}$. (証明終)

3. 不等式はタイトなのか？

結論から言うとタイトです. こちらの記事で紹介したMoore graphを考えます. Moore graph は頂点数$k^2+1$の$k$-正則グラフで, かつ三角形・四角形を含まない($\iff$ 直径$=2$)ものです. Moore graph は $k=2,3,7$に対しては存在しますが, これら三つのグラフは辺数が$\frac{kn}{2}=\frac{k^3+k}{2}$となりますが, この値は辺数の上界$\frac{n\sqrt{n-1}}{2}=\frac{(k^2+1)k}{2}$となり, 辺数と等しくなっています.