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
The starting intuition for this proof is the idea that if a graph $G$ is Hamiltonian, we can draw a diagram of $G$ in which all the vertices are arranged in a circle, and consecutive vertices are adjacent.
For example, the cube graph (below on the left) has a Hamiltonian cycle, and a diagram of the cube graph with the $8$-cycle clearly visible is shown below on the right.
Now let's imagine that the Petersen graph has such a diagram. We don't know yet what the diagram looks like. However, the Petersen graph is $3$-regular, so we know that each vertex we draw must have one additional edge out of it: the "chords", if you will.
Furthermore, one additional property of the Petersen graph is that it does not have any $3$-cycles or $4$-cycles. So the chord out of each vertex must go to one of the three vertices furthest away: anything else would create a $3$-cycle and $4$-cycle. In the diagram below on the right, you see the three possible chords out of the top vertex.
Now, there's two cases. The first is that every chord joins a vertex to the opposite vertex. That gets us the second diagram above, and this is not the Petersen graph: for one thing, it again has $4$-cycles.
So there must be a chord that joins two non-opposite vertices. Such a chord is drawn in the third diagram above. The three red dashed lines are the possible chords out of the bottom vertex, and we see that none of them are possible! Two of them would create $4$-cycles, and one would do worse and create a degree-$4$ vertex.
So our assumption that the Petersen graph had a Hamiltonian cycle must have been wrong.
You ask: can this be generalized? Not meaningfully.
This argument relied on the fact that in a $10$-vertex cycle, if we want to add a chord and not create any $3$-cycles or $4$-cycles, the options are very limited and we can go through all of them and rule them out. In a graph with more vertices, there would be many more possible chords to draw that don't create any $3$-cycles or $4$-cycles.
Already with $12$ vertices, there is a $3$-regular graph with no $3$-cycles or $4$-cycles that has a Hamiltonian cycle:
So all we can say is "If $G$ is a $3$-regular graph on at most $10$ vertices with no $3$-cycles or $4$-cycles, then $G$ is not Hamiltonian", and the Petersen graph is the only graph that matches this description.