Counting the number of squares in a graph

Given an undirected graph, how would one go about calculating the number of squares in the graph? That is, a square is a cycle of length 4.

I know that it is possible to count the number of triangles (cycles with length 3) in polynomial time. Is it possible to calculate the number of squares in polynomial time as well, and how would one go about doing this?

There is a simple $O(n^4)$-time algorithm which I will let you discover yourself. A better algorithm follows from the following formula for the number of squares:
$$
\frac{1}{8} \left( \operatorname{Tr} (A^4) - 2\sum_i d_i^2 + \sum_i d_i \right),
$$
where $A$ is the adjacency matrix and $d_i$ is the degree of the $i$th vertex. Using this formula you can compute the number of squares in $O(n^\omega)$, where $\omega < 2.373$ is the matrix multiplication constant.

To prove the formula, let us expand $\operatorname{Tr} (A^4)$:
$$
\operatorname{Tr}(A^4) = \sum_{i,j,k,\ell} A_{ij} A_{jk} A_{k\ell} A_{\ell i} =
\sum_{\substack{i,j,k,\ell \\ \text{all different}}} A_{ij} A_{jk} A_{k\ell} A_{\ell i} + R,
$$
where $R$ consists of bad terms that we would like to get rid of.

Let's see what these terms look like. Since the diagonal of $A$ consists of zeroes, we have $i \neq j \neq k \neq \ell \neq i$. Hence what could go wrong is $i = k$ or $j = \ell$, or both. Therefore
$$
R =
\underbrace{\sum_{\substack{i,j,\ell \\ i \neq j \neq \ell \neq i}} A_{ij} A_{ji} A_{i\ell} A_{\ell i}}_{R_1} +
\underbrace{\sum_{\substack{i,j,k \\ i \neq j \neq k \neq i}} A_{ij} A_{jk} A_{kj} A_{ji}}_{R_2} +
\underbrace{\sum_{\substack{i,j \\ i \neq j}} A_{ij} A_{ji} A_{ij} A_{ji}}_{R_3}.
$$
It is not hard to check that
$$
\begin{align*}
R_1 &= \sum_i d_i (d_i - 1), \\
R_2 &= \sum_j d_j (d_j - 1), \\
R_3 &= \sum_i d_i
\end{align*}
$$
It follows that
$$
\sum_{\substack{i,j,k,\ell \\ \text{all different}}} A_{ij} A_{jk} A_{k\ell} A_{\ell i} =
\operatorname{Tr}(A^4) - 2 \sum_i d_i^2 + \sum_i d_i
$$
The sum on the left counts each square precisely eight times, leading to the formula stated above.

As an example, consider the square graph on four vertices $1,2,3,4$, which satisfy $d_1 = d_2 = d_3 = d_4 = 2$. Then
$$\operatorname{Tr}(A^4) - 2 \sum_i d_i^2 + \sum_i d_i = 32 - 2 \cdot 4 \cdot 2^2 + 4 \cdot 2 = 8, $$
and indeed there is a single square.

Another example is the complete graph on $n$ vertices. The eigenvalues are $n-1,-1,\ldots,-1$, and so
$$
\operatorname{Tr}(A^4) - 2 \sum_i d_i^2 + \sum_i d_i =
(n-1)^4 + (n-1) - 2n(n-1)^2 + n(n-1) = n(n-1)(n-2)(n-3) = n^{\underline{4}},
$$
and indeed the number of squares is $n^{\underline{4}}/8$.

StackExchange Computer Science Q#64777, answer score: 7