Let $G$ be a graph of order $n$ such that the number of edges in $G$ is $k{n\choose2}$, where $k\in(0,1)$. I am trying to find a lower bound for the number of 4-cycles in $G$.
I was given the hint of trying to bound $\sum_{u\neq v}|N(u)\cap N(v)|$.
I tried to use the expected number of common neighbors for a given pair of vertices, which I got to be $k^2{{n-2}\choose2}$, but I don’t know if that is actually helpful here.
Any help would be appreciated.
Note that number of $4$-cycles that contains $u,v$ as two opposite vertices is $\binom{|N(u) \cap N(v)|}{2}$. Thus, number of $4$-cycles in $G$ is $$\frac 12 \sum_{u \ne v} \binom{|N(u) \cap N(v)|}{2} \ge \frac 14 \left[ \frac{1}{\binom{n}{2}} \left( \sum_{u \ne v} |N(u) \cap N(v)| \right)^2-\sum_{u \ne v}|N(u) \cap N(v)| \right].$$ Hence, it suffices to find the lower bound of $\sum_{u \ne v}|N(u) \cap N(v)|$. We can show that \begin{align*} 2\sum_{u \ne v}|N(u) \cap N(v)| & =\sum_u\sum_{v \ne u}|N(u) \cap N(v)|, \\ &= \sum_u \left( \sum_{v \text{ adjacent }u}|N(v)|-|N(u)| \right), \\ &= \sum_u |N(u)|(|N(u)|-1), \\ & \ge \frac 1n \left( \sum_u |N(u)| \right)^2- \sum_u |N(u)|, \\ & = \frac 1n \left( 2k \binom n2 \right)^2- 2k \binom{n}{2}. \end{align*}