# How many times an empty 4-cycle can be counted in an undirected graph?

I have an undirected graph where each node is labelled with an integer key and I'm asked to detect every simple 4-cycle, which can be seen as an empty square (i.e. the two opposite nodes of the cycle have not to be connected).

I know the labels of a generic square in the graph can be permuted in $4! = 24$ ways, but on his paper (pages 33-36) Cohen states that the symmetric group $S_4$ has $S_4 = 8$ elements, and this should allow me to focus only on $24/8 = 3$ distinct cases.

I don't understand this last point. Well, I know he probably means that the suqare has $8$ isometries (four reflections and four rotations), but I don't understand why this leads to the three cases in Figure 7 of the paper.

Thank you.

For each set $\{a,b,c,d\}$ of four vertices, there are three possible squares: $a-b-c-d$, $a-b-d-c$ and $a-c-b-d$. This is $|S_4|/|D_4|$, where $S_4$ is the symmetric group on four points, and $D_4$ is the dihedral group, the group of symmetries of a square.
Hear a square is a set of edges forming a square. So the squares are really $\{\{a,b\},\{b,c\},\{c,d\},\{a,d\}\}$, $\{\{a,b\},\{b,d\},\{c,d\},\{a,c\}\}$ and $\{\{a,c\},\{b,c\},\{b,d\},\{a,d\}\}$. You can check that all are distinct. Every square on $a,b,c,d$ is one of these — try finding any other one. We know that this list is exhaustive because of the computation $|S_4|/|D_4| = 3$.
• If you consider a square as a set of edges, then there are exactly three possible squares on four vertices. You can write them in several other ways (in fact each one can be written in 8 different ways), and the exact choice is completely arbitrary. For triangles, by the way, the answer is $|S_3|/|D_3| = 6/6 = 1$: there is only one triangle on three vertices. Feb 20, 2014 at 14:53