문제

임의의 $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개의 정점으로 이루어지는 그래프를 세는! 이것보다 많으면 세기 어렵기 때문에 주의가 필요.