問題

任意の$t\geq 2$に対して、$K_{2,t}$を部分グラフとして含まないグラフの最大辺数が次式以下であることを証明せよ。
$$\frac{1}{2}(\sqrt{t-1}n^{3/2}+n)$$

解法

解法を見る

　問題の条件を満たすグラフを$G=(V,E)$とする。$G$に含まれる以下のような部分グラフを考え、これを順序列$M=(v, \{u_1, u_2\})$で表す。$G$に含まれる$M$の数を2通りの方法で数える。

　$\{u_1, u_2\}$を固定し、$v$を探すと、最大で$t-1$個の$v$がありえる。なぜなら、$t$個以上の$v$があれば$K_{2,t}$が$G$に含まれることになってしまうためである。よって
$$ |M| \leq (t-1){n \choose 2} $$が成り立つ。
　一方、$v$を固定して$M$を成すような$\{u_1,u_2\}$を探す。各頂点の次数$d_i=\deg(v_i)$に注目すると、
$$ |M| = \sum_{i\in [n]} {d_i \choose 2} $$となる。
　これらを組み合わせると、
$$|M| = \sum_{i\in [n]} {d_i \choose 2} \leq (t-1){n \choose 2}$$が成り立つ。・・・ (A)
　さらに、コーシーシュヴァルツの不等式と(A)より、

\begin{align}
\sum_{i\in [n]} (d_i - 1) &\leq \sqrt{\sum_{i\in [n]} (d_i-1)^2} \sqrt{\sum_{i∈ [n]} 1}\\
&\leq \sqrt{(t-1)n^2} \times \sqrt{n}
\end{align}

下式を変形し、元の式を見ると、

\begin{align}
2|E| - \sum_{i\in [n]} 1 &\leq & (\sqrt{t-1})n^{3/2}\\
|E| &\leq & \frac{1}{2}(\sqrt{t-1}n^{3/2} + n)
\end{align}

が得られる。

まとめ

コーシーシュヴァルツの不等式を、次数の式に適用するといいことがある。
3つの頂点で成るグラフを数える！これより多いと数えにくいので注意が必要。