Maximum number of cycles of length $4$ If a simple graph has $m$ edges, prove that it has at most $\frac{m^2}{2}$ cycles of length $4$.
 A: 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}$.
A: 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. 
