What's the most efficient algorithm to check the number of cycles of length 4 in an undirected graph? What's the most efficient algorithm to check the number of cycles of length 4 in an undirected, unweighted graph?
 A: You may also go this way: for any vertex $v\in V$, store a bitmask $b_v$ that encodes the positions of its neighbours with a bit $1$. Then run over all the couples $(v_i,v_j)$ with $i\neq j$ and let $N_{i,j}$ be the number of bits $1$ that $b_i$ and $b_j$ share. The number of cycles of length $4$ is given by:
$$ \frac{1}{4}\sum_{i,j}\binom{N_{i,j}}{2}.$$
This is obviously a $O(n^2)$ algorithm both in memory and in time, where $n$ is the number of vertices of the original graph. However, if the graph is very sparse or structured, it may be convenient to compute the number of $4$-cycles through $\text{Tr}(M^2)$ and $\text{Tr}(M^4)$ where $M$ is the adjacency matrix of the graph. I think this is the optimal strategy for sum graphs and Paley graphs, and for every graph whose spectrum is known in advance.
A: I don't know whether this is the fastest possible, but this is how I'd do it if I had to do it fast: Use a hash map that maps pairs of vertices to the number of paths of length $2$ between them. Iterate over the vertices, adding $1$ to the entry for each pair of neighbours of the vertex. Then iterate over the entries, summing $\binom n2$ of the counts $n$. Divide the total by $2$ since you've counted each $4$-cycle twice. (Of course if you're really after speed you'd sum $n(n-1)$ and divide by $4$ in the end.)
