Prove that a simple graph $G$ on $n$ vertices that contains no $K_{2,3}$ has at most $n^{3/2}$ edges.

Question

For each vertex $v_i$, let $N(v_i)$ denote the set of neighbors of $v_i$. Because $G$ does not contain $K_{2,3}$, equivalently we have $|N(v_i) \cap N(v_j)| \leq 2$ for any $i \neq j$. We need to prove that $\sum_i |N(v_i)| \leq 2 n^{3/2}$ subject to the constraints. I can not complete the proof following this line of idea. Any suggestion? Or any simpler proof?

Answer 1

Let $G$ be an $n$-vertex graph that does not contain $K_{2,3}$. Let $m$ be the number of edges of $G$.

We count the number $N$ of pairs $(v,S)$ where $v$ is a vertex of $G$ and $S$ a pair of vertices such that $S\subseteq N(v)$. We count $N$ in two different ways.

First we start with a vertex $v$: each pair $S$ of two vertices from $N(v)$ gives a desired pair $(v,S)$, so $N=\Sigma_v\binom{d(v)}2$.

One the other hand we can start with one of the $\binom n2$ pairs of vertices. Each such pair has at most two common neighbors (or we find $K_{2,3}$), so we find $N\leq 2\binom n2$.

Let $a=\frac{2m}n$ be the average degree of $G$.

Since $\binom x2$ is a convex function we have $\Sigma_v\binom{d(v)}2\geq n\binom a2$.

Combining the equations we get $n\binom a2\leq 2\binom n2$, or $a^2-a\leq 2n-2$.

Substituting $a=\frac{2m}n$ gives a quadratic equation $2m^2-mn-n^2(n-1)\leq0$ and we find $m\leq\frac 14n(1+\sqrt{8n-7})$ and you easily verify that this bound is even stronger than $n^{\frac 32}$.

Answer 2

I find a proof from a paper by Erdos. Below is the detail.

---

Put $d(v_i) = |N(v_i)|$. Without loss of generality, assume that $d(v_1) \geq d(v_2) \geq \cdots \geq d(v_n)$. In addition, let $c(v_i)$ denote the number of $v_i$'s neighbors that are not neighbors of $\{v_1, \cdots, v_{i-1}\}$. Because $G$ does not contain $K_{2,3}$, $|N(v_i) \cap N(v_j)|\leq 2$ for any $j < i$. Hence, $$ c(v_i) \geq d(v_i) - 2(i - 1) $$ Moreover, we have $$ \sum_{i=1}^j c(v_i) \leq n \quad \text{for } j = 1, 2, \cdots, n $$ From the inequalities above, we know that $$ \sum_{i=1}^j (d(v_i) - 2i + 2) \leq n \quad\text{for } j = 1, 2, \cdots, n \tag{1} $$ Put $\alpha = \lfloor n^{1/2} \rfloor$ and $\epsilon = \lfloor n^{1/2} \rfloor - \alpha$. We have from $(1)$ that $$ d(v_1) + d(v_2) + \cdots + d(v_\alpha) \leq n + \sum_{i=1}^\alpha (2i-2) < 2n - 2 \epsilon n^{1/2} \tag{2} $$ Further from $(2)$ and our assumption, we have $$ d(v_i) \leq d(v_\alpha) < \frac{1}{\alpha}(2n - 2\epsilon n^{1/2})=2n^{1/2} \quad \text{for } i = \alpha + 1, \cdots, n \tag{3} $$ By $(2)$ and $(3)$, the number of edges in $G$, denoted as $E(G)$, is upper bounded by $$ E(G) = \frac{d(v_1) + \cdots + d(v_\alpha)}{2} + \frac{d(v_{\alpha + 1}) + \cdots + d(v_n)}{2} < n - \epsilon n^{1/2} + (n - \alpha)n^{1/2} = n^{3/2} $$