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.
How many times an empty 4-cycle can be counted in an undirected graph?
graph theory;graphs
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$.