Since each vertex is labeled with a subset with two elements of $\{1,2,3,4,5\}$, then any permutation of $\{1,2,3,4,5\}$ is going to induce a permutation of the vertices. Moreover, if $\{a,b\}\cap\{c,d\}=\emptyset$, and $\sigma$ is a permutation of $\{1,2,3,4,5\}$, then $\{\sigma(a),\sigma(b)\}\cap\{\sigma(c),\sigma(d)\} = \emptyset$. That is: this permutation of the vertices sends adjacent vertices to adjacent vertices (and non-adjacent vertices to non-adjacent vertices).
Also, two permutations induce the same permutation of the vertices if and only if they are identical permutations (you should prove this). That means that every element of $S_5$ induces a distinct automorphism of the graph.
Are these all the automorphisms, or are there more? If $\tau$ is any automorphism, then by composing with an appropriate permutation of $\{1,2,3,4,5\}$ you may assume that the map fixes $\{1,2\}$; that means that the vertices adjacent to $\{1,2\}$, $\{3,4\}$, $\{3,5\}$, and $\{4,5\}$, must map to each other. Composing with an appropriate permutation (that fixes $1$ and $2$) you may assume that the permutation also fixes $\{3,4\}$; and composing again by a suitable permutation, you can make it fix also $\{3,5\}$ $\{4,5\}$ (again, you need to prove this). So then you are left with an automorphism that fixes $\{1,2\}$ and its three neighbors. If you can show that this is also given by a permutation of $\{1,2,3,4,5\}$, then you will have shown that every automorphism "comes" from an element of $S_5$ (since composing with suitable automorphism that do give you the identity).
It's convenient to work with the Kneser graph interpretation of the Petersen graph: its vertices are the pairs $$\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\}$$ and its edges join the pairs that don't intersect. (For example, $\{1,2\}$ is adjacent to $\{3,4\}$, $\{3,5\}$, and $\{4,5\}$.)
To show that every edge is contained in four $5$-cycles, we prove this for the edge between $\{1,2\}$ and $\{3,4\}$. (This is fine to assume because the Petersen graph is edge-transitive: there is an automorphism sending every edge to this edge.) Then the remainder of the cycle can be chosen as follows:
- The other neighbor of $\{1,2\}$ in the cycle must be $\{x,5\}$ for some $x\in\{3,4\}$.
- The other neighbor of $\{3,4\}$ in the cycle must be $\{y,5\}$ for some $y \in\{1,2\}$.
- The leftover vertex of the cycle must be disjoint from both $\{x,5\}$ and $\{y,5\}$, so it can only be the complement $\{1,2,3,4\} \setminus \{x,y\}$.
Altogether, we have two choices for $x$ and two choices for $y$, so the cycle can be chosen in four ways. We can list out the options: they are
- $\{1,2\}, \{3,4\}, \{1,5\}, \{2,3\}, \{4,5\}$,
- $\{1,2\}, \{3,4\}, \{1,5\}, \{2,4\}, \{3,5\}$,
- $\{1,2\}, \{3,4\}, \{2,5\}, \{1,3\}, \{4,5\}$,
- $\{1,2\}, \{3,4\}, \{2,5\}, \{1,4\}, \{3,5\}$.
Finally, if each of $15$ edges is contained in four $5$-cycles, that gives $15 \cdot 4 = 60$ cycles total; but each cycle is counted $5$ times, once for each of its edges, so the Petersen graph contains $\frac{60}{5} = 12$ cycles.
You also ask if there is a connection between the Petersen graph having $12$ $5$-cycles, a $5$-cycle having $10$ automorphisms, and the Petersen graph having $12 \cdot 10$ automorphisms.
This is certainly not a general rule for all graphs that we can count automorphisms this way. It works for the Petersen graph because it is highly symmetric. We can obtain all $120$ automorphisms as follows:
- Pick any of the $12$ cycles, and decide to map our favorite cycle $\{1,2\}, \{3,4\}, \{5,1\}, \{2,3\}, \{4,5\}$ onto the one we picked.
- Because a cycle has $10$ automorphisms, there are $10$ ways to do this.
- This determines where we send the five vertices of our favorite cycle, and this partial automorphism can be completed to a unique automorphism of the Petersen graph.
It is this "can be completed to a unique automorphism" bit that won't work in general. In other graphs, this can fail in a couple of ways:
- Consider the disconnected graph made up of two $5$-cycles with no edges between them. This has $2 \cdot 10 \cdot 10$ automorphisms: once we decide to map the first cycle to either itself or the second cycle, in one of $10$ ways, we have $10$ ways to complete the automorphism.
- Consider the graph made up of two $5$-cycles with a single edge connecting them. This has only $2$ automorphisms: we can choose to map the first cycle to itself or to the second cycle, but not all automorphisms of the cycle can be completed to an automorphism of the whole graph.
Best Answer
Consider the Petersen graph in the image on the left. I have labeled the vertices via sets, i.e., $12$ is $\{1,2\} = \{2,1\}$ and $34$ is $\{3,4\} = \{4,3\}$ et cetera. If you apply the permutation $(1,4,5,2,3)$ to the vertices, you get a clockwise rotation, that is, $(1,4,5,2,3)$ takes $\{1,2\}$ and maps it to $\{4,3\}$ and so on. The cycle notation $(1,4,5,2,3)$ means $1 \mapsto 4$ and $4 \mapsto 5$ and $5 \mapsto 2$ and $2\mapsto 3$ and $3\mapsto 1$. All you have to do now is the following: If you find a permutation which maps the inner $5$ vertices onto the outer $5$ vertices, the you are finished because then you can mix the two permutations to map every vertex onto every other. Still unclear?