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

Question

Prove that $x\ge \dfrac{n(n-1)(n-3)}8$, where $x$ is the number of $4$-cycles in a graph on $n$ vertices with at least $\displaystyle\frac12\,\binom{n}{2}$ edges.

If there are no $4$-cycles in a graph the edges in $G$, then the number of edges $e(G)$ of $G$ satisfies $$e(G)\le\frac n4(\sqrt{4n-3}+1)\,.$$
But if $e(G)\ge\displaystyle\frac12 {n \choose 2}$, we have to show that the number of $4$-cycles $x$ satisfies $$x \ge \dfrac{n(n-1)(n-3)}8\,.$$ I know that we have to find the difference of edges also the number of cycles of length $4$ is $${n \choose 4}\cdot \frac{3!}2$$ (where $\displaystyle n \choose 4$ is to account for the selection of $4$ vertices and $3!$ for ways of selecting and division by $2$ to delete reverse cycles). But am unable to incorporate the condition on edges and find my result.

Answer 1

Incomplete Solution: This solution works only for $n\geq 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 $v\in 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 $v\neq w$ and $\{u,v\}$ and $\{u,w\}$ are in $E$.

For a fixed $u\in V$, there are $\displaystyle\binom{d_u}{2}$ sets of the form $\{v,w\}\in\displaystyle\binom{V}{2}$ such that $\{u,v\},\{u,w\}\in E$. Hence, $\displaystyle |S|=\sum_{u\in V}\,\binom{d_u}{2}$. Now, for $\{v,w\}\in\displaystyle\binom{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\}\in\binom{V}{2}}\,t_{\{v,w\}}=2x\,.$$ Furthermore, for $\{v,w\}\in\displaystyle\binom{V}{2}$, we have $t_{\{v,w\}}=\displaystyle\binom{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\}\in\binom{V}{2}}\left(\frac{1}{2}+ \sqrt{2\,t_{\{v,w\}}+\frac{1}{4}}\right)=\frac{1}{2}\binom{n}{2}+\sum_{\{v,w\}\in\binom{V}{2}}\sqrt{2\,t_{\{v,w\}}+\frac{1}{4}}\,.$$ Due to the concavity of the function $t\mapsto\sqrt{t}$ for $t\in[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\}\in\binom{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_{u\in V}\,\binom{d_u}{2} \geq n\,\binom{\frac{1}{n}\sum_{u\in V}\,d_u}{2}=n\,\binom{2m/n}{2}=m\left(\frac{2m}{n}-1\right)\,.$$ That is, $$\frac{1}{2}\binom{n}{2}+\binom{n}{2}\sqrt{\frac{4x}{\binom{n}{2}}+\frac{1}{4}}\geq |S| \geq m\left(\frac{2m}{n}-1\right)\,.$$ 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}-1\right)\left(\frac{m}{\binom{n}{2}}\left(\frac{2m}{n}-1\right)-1\right)\,.$$ In particular, if $m\geq\displaystyle\frac{1}{2}\binom{n}{2}$ and $n\geq 7$, then we have $$x \geq \frac{1}{8}n(n-1)\left(\frac{n-1}{2}-1\right)\left(\frac{1}{2}\left(\frac{n-1}{2}-1\right)^{\vphantom{2^{2^2}}}-1\right)=\frac{n(n-1)(n-3)(n-7)}{64}\,.$$ If $n\geq 15$, then $\dfrac{n-7}{8}\geq 1$, so $x\geq\dfrac{n(n-1)(n-3)}{8}$.

P.S. For $n \leq 3$, the inequality $x\geq\dfrac{n(n-1)(n-3)}{8}$ is vacuously true. For $4\leq n\leq 10$, the inequality $x\geq\dfrac{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$).

Answer 2

Lemma. If $a_i\in\mathbb N_0$ for $1\le i\le N$ and $\sum a_i\ge 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}N\ge \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\\ &\ge\frac1N\left(\sum a_i\right)^2-\sum a_i\\ &=\left(\frac 1N\sum a_i-1\right)\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 ${d\choose 2}$ paths of length $2$. Thus using the lemma with $\sum_v d(v)=2e(G)\ge\frac{n(n-1)}2$, the number of length 2 paths is $$ n_2\ge\frac{(\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_2\ge \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-{n\choose 2})\frac{n(n-1)(n-3)}8}{2{n\choose 2}} =\frac{n(n-1)(n-3)(n-7)}{64}.$$ For $n\ge 15$, this implies the desired result.

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