組合せの技法 | 場合の数と確率統計

1 三角形を含まないグラフ

定理 1.1 (Mantel 型の上界). $n$ 頂点の単純無向グラフが三角形を含まないならば、辺数 $m$ は

m\le\left\lfloor\frac{n^2}{4}\right\rfloor

を満たします。この上界は達成されます。

証明. $m=0$ ならば結論は明らかです。以下では $m>0$ とします。

辺 $uv$ を一つ取ります。 $u$ と $v$ に共通の隣接頂点があればグラフは三角形を含むので、両端の次数は

d(u)+d(v)\le n

を満たします。すべての辺について足すと、各頂点 $v$ の次数 $d(v)$ が、その頂点に接続する各辺について一回ずつ現れるので、

\sum_{v}d(v)^2 =\sum_{uv\in E}(d(u)+d(v)) \le mn

です。

また、平方完成またはコーシー・シュワルツの不等式と握手補題から、

\sum_vd(v)^2\ge\frac{\left(\sum_vd(v)\right)^2}{n} =\frac{4m^2}{n}

です。したがって $4m^2/n\le mn$ です。 $m>0$ なので $m$ で割ると $m\le n^2/4$ を得ます。 $m$ は整数なので $m\le\lfloor n^2/4\rfloor$ です。

頂点を個数が $\lfloor n/2\rfloor$ と $\lceil n/2\rceil$ の二群へ分け、異なる群の頂点をすべて辺で結び、同じ群の内部には辺を置きません。この完全二部グラフは三角形を含まず、辺数は

\left\lfloor\frac n2\right\rfloor \left\lceil\frac n2\right\rceil =\left\lfloor\frac{n^2}{4}\right\rfloor

です。したがって上界は達成されます。▨

証明では、各辺の局所条件を全辺について足し合わせ、握手補題によって全体の辺数へ変換しました。

1では3頂点と4頂点の二群に分け、群間の辺をすべて結ぶと $3\cdot4=12$ 本です。2では共通の隣接頂点が存在すると、その頂点と $u,v$ が三角形を作ります。3では $m=0$ のとき0で割る操作が定義されません。4は頂点と接続辺の組を頂点側と辺側から数えます。