I have a graph theory problem that I can't figure out how to solve. The problem is:
- Prove that if $G$ is a simple graph with $n$ vertices and $$\sum_{v\in V(G)}\binom{d(v)}{2} > (m-1)\binom{n}{2}$$ Then $G$ contains $K_{2,m}$
- Use 1. to prove that for $n\geq 4$, every $n$-vertex graph with more than $2n^{3/2}$ edges has girth at most 4.
I understand that the sigma sums all the paths of length 2 in the graph but I don't know what to do with this information. I would be happy to get some guidance here. Thank you
(i) Make a new bipartite graph, in first part are pairs of vertices of starting graph and in the second pair are the vertices of a starting graph. Connect every pair of vertices $\{u,v\}$ with a vertex $w$ if both of them are connected with $w$.
Suppose that every pair $\{u,v\}$ has degree at most $m-1$. Since every vertex $v$ is connected to ${d(v)\choose 2}$ pairs.
Then we get a reversed inequality: $$\sum _{v\in V}{d(v)\choose 2}\leq (m-1){n\choose 2}$$ A contradiction.
(ii) Suppose there is no $K_{2,2}$ (i.e. 4-cycle) in the graph. Then we have ($m=2$) $$\sum _{v\in V}{d(v)\choose 2}\leq {n\choose 2}$$
By Cauchy-Shwarz inequality and Handshake lemma we have $$ \sum _{v\in V}{d(v)\choose 2}\geq {{1\over n} 4\varepsilon^2 -2\varepsilon \over 2}$$
So we get $$n^2(n-1) \geq 4(4n^3)-n 4n^{3\over 2}$$ which clearly does not hold for $n\geq 4$.