# Is there an algorithm or a set of rules for creating new permutation formulas for labeling the vertices of an undirected “graph sketch”?

Let's say we have a sketch of an underected graph like the one below:

And we are told to count the ways we can seat 5 people on those chairs (if the vertices are chairs). So this is a permutation problem, with the condition that we have some symmetries in the arrangement of the chairs, so that if we neglect the symmetries, we may count some cases more than once (which is not correct).

If, instead of the graph above, we had a cycle (like a ring) $C_n$, then I would say that there are $\frac12 (n-1)!$ ways to seat those people on the chairs (the vertices of $C_n$). But how can we make a permutation formula for new graph sketches like the one above?

Any idea? Are there any rules of thumb which are useful? or an algorithm?

Arthur’s answer shows how to calculate this for your specific case, but doesn’t mention the tools you need to generalize this, so I wanted to expand on his answer a bit.

The concept we need to understand to approach this problem in general is the automorphism group of a graph, $\text{Aut}(G)$. The number of distinct ways to label a graph, up to isomorphism is always given by $$\frac{n!}{|\text{Aut}(G)|}.$$

Calculating the size of the automorphism group of a graph in general is hard(it is at least as hard as the graph isomorphism problem.) but almost all graphs have trivial automorphism group, so for some applications this can be circumvented.

The number of essentially distinct seating arrangements is $n!$ divided by the number of permutations that you consider would give rise to "the same" configuration. For instance, for the cyclic case, the are $2n$ such transformations ($n$ rotations, and $n$ reflections).
In your case, there are $8$ permutations (the top left vertex is special, and the remaining four give $C_4$, which by the above gives $4+4=8$), so there are $120/8=15$ essentially different seating arrangements.