Prove that $xge n(n-1)(n-3)/8$, where $x$ is the number of $4$-cycles in a graph on $n$ vertices with at least $frac12binom{n}{2}$ edges.

Lemma. If $a_iinmathbb N_0$ for $1le ile N$ and $sum a_ige M>0$ then $$sum_{i=1}^N{a_i choose 2}ge frac{(M-N)M}{2N}$$

Proof. Using the QM-AM inequality $$ frac{sum_i a_i^2}Nge left(frac{sum_i a_i}{N}right)^2$$ we find $$begin{align}2 sum_{i=1}^N{a_i choose 2} &=sum a_i^2-sum a_i\ &gefrac1Nleft(sum a_iright)^2-sum a_i\ &=left(frac 1Nsum a_i-1right)sum a_i\ &ge frac{(M-N)M}{N}end{align}$$ where the last inequality is justified even when the expressin in parentheses is negative because the left hand side is certainly non-negative. $_square$

Each vertex of degree $d$ gives rise to ${dchoose 2}$ paths of length $2$. Thus using the lemma with $sum_v d(v)=2e(G)gefrac{n(n-1)}2$, the number of length 2 paths is $$ n_2gefrac{(frac{n(n-1)}2-n)frac{n(n-1)}2}{2n}=frac{n(n-1)(n-3)}{8}$$

For two distinct vertices $a,b$ let $f(a,b)$ be the number of $2$-paths from $a$ to $b$ (i.e., the number of common neighbours). Then $$sum_{{a,b}}f(a,b)=n_2ge frac{n(n-1)(n-3)}8$$ and $$2x = sum_{{a,b}}{f(a,b)choose 2}$$ so that by the lemma $$x ge frac{(frac{n(n-1)(n-3)}8-{nchoose 2})frac{n(n-1)(n-3)}8}{2{nchoose 2}} =frac{n(n-1)(n-3)(n-7)}{64}.$$ For $nge 15$, this implies the desired result.

After getting rid of the mistakes Batominovski kindly noticed, the result is of course the same as his. :(

Incomplete Solution: This solution works only for $ngeq 15$.

Write $V$ and $E$ for the set of vertices and the set of edges of $G$, respectively. Let $n:=|V|$, $m:=|E|$, and $x$ the number of $4$-cycles in $G$. For $vin V$, write $d_v$ for the degree of $v$. Let $S$ be the set of all pairs $big(u,{v,w}big)$, where $u,v,w in V$ are such that $vneq w$ and ${u,v}$ and ${u,w}$ are in $E$.

For a fixed $uin V$, there are $displaystylebinom{d_u}{2}$ sets of the form ${v,w}indisplaystylebinom{V}{2}$ such that ${u,v},{u,w}in E$. Hence, $displaystyle |S|=sum_{uin V},binom{d_u}{2}$. Now, for ${v,w}indisplaystylebinom{V}{2}$, let $t_{{v,w}}$ be the number of $4$-cycles such that $v$ and $w$ are opposite vertices. Note that $$sum_{{v,w}inbinom{V}{2}},t_{{v,w}}=2x,.$$ Furthermore, for ${v,w}indisplaystylebinom{V}{2}$, we have $t_{{v,w}}=displaystylebinom{r_{{v,w}}}{2}$, where $r_{{v,w}}$ is the number of common neighboring vertices of $v$ and $u$. Clearly, $$|S|=sum_{{v,w}in binom{V}{2}},r_{{v,w}},.$$

Observe that $left|r_{{v,w}}-dfrac{1}{2}right|=sqrt{2,t_{{v,w}}+dfrac{1}{4}}$, so $r_{{v,w}}leq dfrac{1}{2}+ sqrt{2,t_{{v,w}}+dfrac{1}{4}}$. Thus, $$|S| leq sum_{{v,w}inbinom{V}{2}}left(frac{1}{2}+ sqrt{2,t_{{v,w}}+frac{1}{4}}right)=frac{1}{2}binom{n}{2}+sum_{{v,w}inbinom{V}{2}}sqrt{2,t_{{v,w}}+frac{1}{4}},.$$ Due to the concavity of the function $tmapstosqrt{t}$ for $tin[0,infty)$, we have by Jensen's Inequality that $$|S| leq frac{1}{2}binom{n}{2}+binom{n}{2}sqrt{frac{1}{binom{n}{2}}sum_{{v,w}inbinom{V}{2}}left(2,t_{{v,w}}+frac{1}{4}right)}=frac{1}{2}binom{n}{2}+binom{n}{2}sqrt{frac{4x}{binom{n}{2}}+frac{1}{4}},.$$

By the Cauchy-Schwarz Inequality, $$|S|=sum_{uin V},binom{d_u}{2} geq n,binom{frac{1}{n}sum_{uin V},d_u}{2}=n,binom{2m/n}{2}=mleft(frac{2m}{n}-1right),.$$ That is, $$frac{1}{2}binom{n}{2}+binom{n}{2}sqrt{frac{4x}{binom{n}{2}}+frac{1}{4}}geq |S| geq mleft(frac{2m}{n}-1right),.$$ Ergo, if $m$ is sufficiently large (namely, $m geq dfrac{n}{4}left(1+sqrt{4n-3}right)$), then $$x geq frac{m}{4}left(frac{2m}{n}-1right)left(frac{m}{binom{n}{2}}left(frac{2m}{n}-1right)-1right),.$$ In particular, if $mgeqdisplaystylefrac{1}{2}binom{n}{2}$ and $ngeq 7$, then we have $$x geq frac{1}{8}n(n-1)left(frac{n-1}{2}-1right)left(frac{1}{2}left(frac{n-1}{2}-1right)^{vphantom{2^{2^2}}}-1right)=frac{n(n-1)(n-3)(n-7)}{64},.$$ If $ngeq 15$, then $dfrac{n-7}{8}geq 1$, so $xgeqdfrac{n(n-1)(n-3)}{8}$.

P.S. For $n leq 3$, the inequality $xgeqdfrac{n(n-1)(n-3)}{8}$ is vacuously true. For $4leq nleq 10$, the inequality $xgeqdfrac{n(n-1)(n-3)}{8}$ is false (there are easy counterexamples). I am tired looking for other counterexamples, but I believe that the inequality is false for $n=11,12,13$ (but not sure for $n=14$).