Maximum number of cycles of length $4$

Question

If a simple graph has $m$ edges, prove that it has at most $\frac{m^2}{2}$ cycles of length $4$.

Answer 1

Let $A$ denote the adjacency matrix of a simple graph $G(V,E)$ on $n$ vertices with $m$ edges. Since $A$ is symmetric, it has real eigenvalues $\lambda_1,\lambda_2,\ldots,\lambda_n$. The diagonal entries of $A^2$ are the degrees of the vertices in $G$. Thus $$\sum_{i=1}^n\lambda_i^2=\sum_{v\in V}\deg v=2m.$$ Note that the diagonal entry of $A^4$ corresponding to the vertex $v$ of $G$ is the number of circuits $(v_0,v_1,v_2,v_3,v_4)$ such that each $\{v_i,v_{i+1}\}$ is an edge and $v_0=v_4=v$. Hence, $N=\sum_{i=1}^n\lambda_i^4$ is the sum of all diagonal entries of $A^4$, which is the number of such circuits.

If $\gamma$ is the number of cycle of lengths $4$, then each of such cycles is counted $8$ times in $N$ (there are four starting points and two orientations). Furthermore, there are $\sum_{v\in V}(\deg v)^2$ circuits of the form $(v_0,v_1,v_2,v_3,v_4)$ where $v_0=v_2=v_4$. Finally, there are $\sum_{v\in V}\Big((\deg v)^2-\deg v\Big)$ circuits of the form $(v_0,v_1,v_2,v_3,v_4)$ where $v_0=v_4\neq v_2$ and $v_1=v_3$. That is, $$N=8\gamma+\sum_{v\in V}(\deg v)^2+\sum_{v\in V}\Big((\deg v)^2-\deg v\Big).$$ Hence, $$N=8\gamma+\sum_{v\in V}\deg v+2\sum_{v\in V} \Big((\deg v)^2-\deg v\Big)\geq 8\gamma +\sum_{v\in V}\deg v.$$ Since $\sum_{v\in V}\deg v=2m$ and $$N=\sum_{i=1}^n\lambda_i^4\leq \left(\sum_{i=1}^n\lambda_i^2\right)^2=(2m)^2=4m^2,$$ we obtain $$\gamma\leq \frac{4m^2}{8}-\frac{2m}{8}=\frac{m^2}{2}-\frac{m}{4}.$$

In general, the number of cycles of length $2k$ of $G$ is less than or equal to $\frac{2^{k-2}m^k}{k}$. This bound is quite weak, however.

Answer 2

Let $L$ denote the number of disjoint pairs of edges (ie pairs of edges with no vertex in common).
Then $L$ is bounded above by the number of pairs of distinct edges (since we are dropping the 'disjoint' condition), hence: $$L\leq{m\choose2}$$ Now let $c$ denote the number of cycles of length 4 in the graph. Each cycle of length 4 contains exactly two pairs of disjoint edges. For example, if the 4-cycle is $xyzwx$ the two pairs are $(xy,zw)$ and $(yz,wx)$.

On the other hand, each pair of disjoint edges is contained in at most two 4-cycles. For example, suppose $ab$ and $cd$ are two disjoint edges; then, the only 4-cycles which contain both $ab$ and $cd$ are $abcda$ and $abdca$ (although it's not necessarily true that the graph conatins these cycles).
Hence we have:

$$2c\leq 2L$$

Combining the two inequalities we get $c\leq{m\choose2}\leq\frac{m^2}{2}$.