Using Polya and Cycle Index

Question

I have a D6 hexagon with edges connecting vertices 1,3,5 and 2,4,6. I'm supposed to find the number of different, proper colorings for the shape with 4 colors. I'm considering the symmetries and building a cycle index, I've noted that odd rotations around the shape will not create a symmetry due to the inner edges, but I think I'm still lost on how to be thinking about the symmetries. Mostly in the sense of, how should I be considering what cases to exclude without having to explicitly list out a bunch of examples? I feel like there's more straightforward ways to thinking about it, but I'm too lost in the numbers and colors of it all. Tips and tricks would be helpful, or general advice on how I might approach the problem from a different viewpoint.

Problem Image

Christophe Boilley · Accepted Answer · 2025-11-27 08:58:00Z

A permutation on the vertices of your graph is an automorphism if and only if it preserves opposite vertices (i.e. the image of $1$ must be the opposite of the image of $4$ and so on). Then in all cases below, you don't have to care about the position of pairs of opposite vertices.

Two vertices may be of the same color only if they are opposite. So you cannot use less than three colors and you cannot have more than one pair of opposite vertices with two different colors.

When opposite vertices share the same color, you just have to choose three colors among four.

When one pair of opposite vertices have different colors, you have to choose these two colors, and the other colors will be left to the other pairs of opposite vertices.

Finally, the number of proper colorings with (at most) four colors is $\binom 43+\binom 42=10$.

Stack Exchange Network

Using Polya and Cycle Index

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Using Polya and Cycle Index

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions