Counting the number of polygons in a figure

Solution 1:

This post illustrates why $\text{Tr}(A^k)$ gives the number of cycles of length $k$ in the graph with adjacency matrix $A$. We have to be careful since a cycle is not the same thing as a polygon. For example, we can make a 4-cycle by moving between two nodes only: XYXY is a 4-cycle, but not a quadrilateral.

For triangles it turns out that this is not a problem since you can't form a 3-cycle that isn't also a triangle. (Caveat: you might form a degenerate (flat) triangle if three nodes are colinear. There is no way of detecting whether points are colinear using an abstract graph, represented as an adjacency matrix.)

Even with triangles, we still have to be careful of double counting. $\text{Tr}(A^3)$ is the number of 3-cycles in an undirected graph, but this gives 6 for the simple case of a 3-node graph that is itself triangle. $$A=\left(\begin{array}{ccc}0&1&1\\1&0&1\\1&1&0\end{array}\right) \Rightarrow \text{Tr}(A^3)=6$$ This is because all of the following cycles are triangles, even though they all form the same triangle: XYZ, XZY, YXZ, YZX, ZXY, ZYX.

Since each triangle gets counted 6 times, the total number of triangles in a graph with adjacency matrix $A$ is $$\text{Tr}(A^3)/6 = \text{Tr}(A^3)/3!$$

The example in the original question will have quite a few degenerate triangles since there are so many colinear vertices, making this method less than ideal. You can however compute all the triangles using the trace of the adjacency matrix and then try to count and subtract the number of degenerate triangles.