Distinct edge permutations in a 4-state graph

Question

For this type of 4-state graph with 3 different edges, {←, →, ↔}
and no diagonal connection between the vertices S1, S2, S3, S4 allowed.
I wished to calculate all the distinct edge permutations,
meaning the symmetric edge permutations are counted only once.

At first, I calculated all the different permutations (repetition allowed) as $3^4$ = 81
However, I can't find a simple, straightforward way to rule out the symmetric permutations.

Answer 1

Welcome to the wonder that is Burnside's lemma. First, you have to find the collection of all symmetry operations you consider would give rise to the "same" final configuration. In this case, I assume that you mean rotations by $90^\circ$ clockwise and counterclockwise, rotation by $180^\circ$, as well as reflection along the horizontal, vertical and the two diagonal axes. Also, don't forget the trivial symmetry: doing nothing.

There are thus $8$ such operations. The collection of all of these is usually called either $D_4$ or $D_8$, the dihedral group with eight elements, or the symmetry group of the square. That is only somewhat important to us, but it's a nice bit of trivia.

For each of these $8$ operations, count the number of graphs that are entirely indistinguishable before and after applying said transformation. Sum it all up, then divide by $8$, and that's your answer.

• The trivial transformation. There are, as you have already calculated, $81$ graphs, and for each one of them, they are indistinguishable ("invariant") from the result of applying the transformation
• $90^\circ$ rotation clockwise. In this case, if a graph is to be indistinguishable from the result of applying the transformation, then all arrows have to be the same. Thus there are $3$ valid graphs for this transformation
• $90^\circ$ counterclockwise also has $3$ graphs
• $180^\circ$ rotation. Here the two opposite sides are forced to have reverse arrows, but otherwise you're free to choose, so there are $3\cdot 3 = 9$ different invariant graphs
• Reflection along horizontal axis. The two vertical arrows must be double-headed, and the two horizontal arrows must be mirror images of one another, but you are free to choose which arrow that should be. Thus $3$ invariant graphs
• Reflection along vertical axis also has $3$ invariant graphs
• Reflection along the top left-bottom right diagonal. Here the two edges incident to the top left vertex must be mirror images of one another, and same for the two edges incident to the bottom right vertex. Therefore $9$ invariant graphs
• Reflection along the top right-bottom left diagonal also has $9$ invariant graphs

Thus the number of distinct graphs is $$ \frac{81 + 3 + 3 + 9 + 3 + 3 + 9 + 9}{8} = 15 $$