# 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?

• What have you tried? Did you look at the algorithm for counting triangles? Maybe you can generalize it to squares. – adrianN Oct 18 '16 at 9:58

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: $$\operatorname{Tr} (A^4) - \sum_i d_i^2,$$ 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.