Counting cycles on unlabelled graphs

207 Views Asked by At

I'm doing a problem for an assignment and I've been asked to determine the number of cycles of length 6 on a Petersen graph with reference to the one in the text and handbook. The book shows the standard pentagram in a pentagon layout and the vertices and edges are unlabelled.

So far, I have identified two distinct cycles of length 6.

two cycles of the Petersen graph

My question is: since, by symmetry, I can rotate these cycles around to five different sets of vertices, do I have 10 cycles or are there only two because the graph is unlabelled and therefore any of the 5 copies would be indistinguishable?

I know that the vertices are different for each copy, but without labels, I cannot define the cycle to someone else and they will see it depending on the orientation from which they view the graph.

1

There are 1 best solutions below

0
On BEST ANSWER

You have $10$ cycles. Graph labelling is only meaningful when comparing two graphs. Even though the vertices are not labeled, they are different elements of the vertex set, and so the cycles are distinguishable as well.