What is $\operatorname{ex}(n, K_{2,3})$?

Question

What is the maximum number of edges in a Graph on $n$ vertices that does not include $K_{2,3}$ as an induced subgraph? (i.e. what is $\operatorname{ex}(n, K_{2,3})$?)

I'm having difficulty in linking the theory (proofs) to actually applying it in a question. The way I'm thinking of it is every set of $2$ vertices in $G$ should be connected to at most $2$ other vertices. Then, would $\operatorname{ex}(n, K_{2,3})$ be something along $ \leq {n\choose 2} \cdot 2$? I don't know if I'm seeing it correctly or even how to proceed. Would appreciate any help!

Answer 1

Hints: If no $K_{2,t}$ exists,

1. Clearly we can ignore isolated vertices, so henceforth $ d_ i \geq 1$.
2. Show that $\sum {d_i \choose 2 } \leq (t-1) { n \choose 2} $.
3. Show that this implies (say) $ \sum (d_i -1)^2 \leq (t-1) n^2$.
4. Show that this implies (say) $ \sum d_i \leq \sqrt{t-1} n^{3/2} + n $.

Note: Of course this isn't a tight bound. I don't think a tight bound easily exists for such questions (unless it's quite trivial), and at best you can ask for an asymptotic bound.

Answer 2

The number of edges of graph $G$ without $K_{2,3}$ can be estimated like this:

1. Prove that $\operatorname{deg}(u)+\operatorname{deg}(v)\leq n+2$ for all $u,v\in V(G)$ and $u\neq v$.

2. From this, deduce that $|E(G)|\leq n(n+2)/4$.