Help with Polya Counting question

Question

So I have this graph:

And I want to figure out how many different (they are identical when they differ by an element of the symmetry group of the graph) iterations can be made when each node in the graph is colored one of two colors. Now, I tried using Polya counting but I don't get a full number, so i must be doing something wrong. Would appreciate if someone could do the Polya counting for the Hexagon portion, as I think that's where I am making the mistake.

Answer 1

First, consider the set of permutations you are allowing yourself: if you are only considering the hexagonal portions of the graph to be isomorphic if they are flipped over the horizontal axis, then there is only the identity permutation $(1\ 2\ 3\ 4\ 5\ 6) \rightarrow (1\ 2\ 3\ 4\ 5\ 6) = I$, and the flip permutation $(1\ 2\ 3\ 4\ 5\ 6) \rightarrow (1\ 6\ 5\ 4\ 3\ 2) = (26)(35)$. Therefore, the cyclic index for this portion of the graph is $Z(G_H)=\frac{1}{2}(a_1^6+a_1^2a_2^2)$. For this alone, when we allow $a_1=x+y$ and $a_2=x^2+y^2$, and then further allow $x=y=1$, we see that there are $40$ unique ways to 2-color this graph.

Now, for the triangular portion of the graph, we can use a very similar method to see that $Z(G_T)=\frac{1}{2}(a_1^3+a_1a_2)$, and by making the same substitutions, we see that there are $6$ ways you can 2-color this portion of the graph. However, note that it is not possible for every coloring of the hexagonal portion to appear with every coloring of the triangular portion. For example, you cannot simultaneously have every vertex of the hexagon blue while every vertex of the triangle is red. For this reason, for any coloring of the hexagonal portion, there are only $3$ unique ways to color in the remaining two vertices of the triangle.

Finally, taking into consideration the singleton vertex, we see that there are $40\times 3\times 2=240$ unique ways to 2-color this graph under the given restrictions.

Answer 2

We start by computing the cycle index. We have four permutations in the automorphism group of the fish. All of them must fix the vertex where the tail is attached as well the eye and the tip of the mouth, for a contribution of $a_1^3.$ First permutation fixes everything, giving $a_1^9.$ Second permutation, fixes tail, flips body, for $a_1^5 a_2^2.$ Third permutation, fixes body, flips tail, for $a_1^7 a_2.$ Fourth permutation, flips tail and flips body, for $a_1^3 a_2^3.$ We thus have the cycle index

$$Z(F) = \frac{1}{4} (a_1^9 + a_1^5 a_2^2 + a_1^7 a_2 + a_1^3 a_2^3).$$

Now by the Polya Enumeration Theorem (PET) the generating function for two-colorings say black and white is given by

$$Z(F; B+W) = \frac{1}{4} ((B+W)^9 + (B+W)^5 (B^2+W^2)^2 \\ + (B+W)^7 (B^2+W^2) + (B+W)^3 (B^2+W^2)^3) \\ = {B}^{9}+6\,{B}^{8}W+19\,{B}^{7}{W}^{2}+39\,{B}^{6}{W}^{3} +55\,{B}^{5}{W}^{4}+55\,{B}^{4}{W}^{5} \\ +39\,{B}^{3}{W}^{6}+19\,{B}^{2}{W}^{7}+6\,B{W}^{8}+{W}^{9}.$$

So there are $39$ colorings with six black nodes and three white ones. We are only interested in the total count, however. Hence we seek (set $B=W=1$ for the count)

$$Z(F;2,2)= \frac{1}{4} (2^9 + 2^7 + 2^8 + 2^6) = 240$$

same as in the answer that was first to appear. This was Burnside (fixed assignments must be constant on the cycles, giving two possibilities for each cycle).