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

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

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

上の証明では、各辺の両端の次数について成り立つ不等式を全辺について足し合わせ、握手補題を用いて、次数の和を辺数で表しました。

2 演習

問題 2.1. $n=7$ のとき、定理 1.1の証明で上界を達成するために用いたグラフの構成が、三角形を含まず、辺を12本もつことを確かめよ。

解答.

7個の頂点を、3頂点の群と4頂点の群に分ける。異なる群の頂点をすべて辺で結び、同じ群の内部には辺を置かない。三つの頂点を選ぶと、群は二つしかないので、少なくとも二つの頂点が同じ群に属する。同じ群の二頂点は辺で結ばれていないので、どの三頂点も三角形をなさない。辺は、3頂点の群の頂点と4頂点の群の頂点の組ごとに1本ずつあるので、辺の数は $3\cdot4=12$ 本である。この値は $\lfloor7^2/4\rfloor=\lfloor49/4\rfloor=12$ に等しい。▨

問題 2.2. $n$ 頂点の単純無向グラフが三角形を含まないとき、辺 $uv$ に対して $d(u)+d(v)\le n$ が成り立つ理由を、共通の隣接頂点に着目して説明せよ。

解答.

$u$ に隣接する頂点の集合を $N(u)$ 、 $v$ に隣接する頂点の集合を $N(v)$ とすると、 $|N(u)|=d(u)$ 、 $|N(v)|=d(v)$ である。 $N(u)\cap N(v)$ に頂点 $w$ が属すると仮定すると、 $uv$ 、 $uw$ 、 $vw$ がすべて辺になり、 $u,v,w$ は三角形をなす。グラフは三角形を含まないので、 $N(u)\cap N(v)=\varnothing$ である。 $N(u)$ と $N(v)$ はともに $n$ 個の頂点の集合の部分集合であり、互いに交わらないので、

d(u)+d(v)=|N(u)|+|N(v)|=|N(u)\cup N(v)|\le n

が成り立つ。▨

問題 2.3.定理 1.1の証明で、 $m=0$ の場合を分けずに不等式 $4m^2/n\le mn$ を $m$ で割ると、どのような問題が生じるか。

解答.

$m=0$ のとき、不等式 $4m^2/n\le mn$ は $0\le0$ となって成り立つが、両辺を $m$ で割る操作は0による除算であり、定義されない。また、不等式の両辺を割って不等号の向きを保つことができるのは、正の数で割る場合である。したがって、 $m$ で割る段は $m>0$ のときに限って正しく、 $m=0$ の場合の結論 $m\le\lfloor n^2/4\rfloor$ は別に確かめる必要がある。 $m=0$ のときは、 $0\le\lfloor n^2/4\rfloor$ が直接成り立つ。▨

問題 2.4. $n$ 頂点の単純無向グラフの辺数を $m$ とする。次数の総和が $2m$ であることを、二通りに数える方法で証明せよ。

解答.

頂点 $v$ と、 $v$ を端点とする辺 $e$ の組 $(v,e)$ の個数を数える。頂点ごとに数えると、頂点 $v$ を端点とする辺は $d(v)$ 本あるので、組の個数は $\sum_vd(v)$ である。辺ごとに数えると、単純無向グラフの各辺は相異なる二つの頂点を端点にもつので、各辺について組は2個あり、組の個数は $2m$ である。二つの数え方は同じ組を重複なく数えているので、 $\sum_vd(v)=2m$ が成り立つ。▨

§B4.22組合せの技法

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

2 演習

前提記事