The comments gave many resources for finding the longest cycle in such a graph.
This is (not) the longest cycle in a graph. I will give a counterexample of length 85.
1 > 12 > 13 > 14 > 5 > 6 > 7 > 8 > 18 > 19 > 20 > 30 > 40 > 50 > 60 > 70 > 80 > 90 > 100 > 99 > 98 > 97 > 96 > 95 > 94 > 93 > 84 > 85 > 86 > 87 > 88 > 89 > 79 > 69 > 68 > 78 > 67 > 77 > 76 > 75 > 74 > 64 > 65 > 66 > 56 > 57 > 58 > 48 > 39 > 38 > 37 > 28 > 27 > 17 > 16 > 15 > 25 > 36 > 46 > 35 > 45 > 55 > 54 > 44 > 33 > 32 > 42 > 43 > 53 > 52 > 62 > 72 > 73 > 83 > 82 > 92 > 91 > 81 > 71 > 61 > 51 > 41 > 31 > 21 > 11 > 1
After running the longest cycle algorithm on Mathematica for quite some time, a longest cycle (of length 89) in the graph is as below:
1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 18 > 19 > 20 > 30 > 40 > 50 > 60 > 70 > 80 > 90 > 100 >
99 > 98 > 97 > 96 > 95 > 94 > 93 > 84 > 85 > 86 > 87 > 88 > 89 > 79 > 69 > 68 > 78 >
67 > 77 > 76 > 75 > 74 > 64 > 65 > 66 > 56 > 57 > 58 > 48 > 39 > 38 > 37 > 28 > 27 >
17 > 16 > 15 > 25 > 36 > 46 > 35 > 45 > 55 > 54 > 44 > 33 > 24 > 13 > 23 > 22 > 32 >
42 > 43 > 53 > 52 > 62 > 72 > 73 > 83 > 82 > 92 > 91 > 81 > 71 > 61 > 51 > 41 > 31 >
21 > 11 > 1
To answer your second question, the length of the longest cycle is also known as the graph circumference. That should give you a keyword to start exploring how one might get such a length. There are many ways to find the longest cycle, one of the simplest is a simple modification from the Hamiltonian cycle algorithm.
This is however an NP-complete problem.
Here is the graph in the adjlist format should anyone wants to verify the above solution.
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
For point $1$, Imagine the (hypothetical) $7-$cycle $C$ as a heptagon. The proposed "additional edge" is a diagonal of this heptagon. The statement is equivalent to saying that any such diagonal cuts the heptagon in to two pieces, one of which is a triangle or quadrilateral. Because the Petersen graph has no cycles of length $\lt5$, it means that the vertices in such a $C$ cannot be connected to each other except by the edges that are part of $C$.
Point $2$ follows directly from this and the fact that every vertex of the Petersen graph has degree $3$: since they each vertex in $C$ has $2$ edges in $C$, they must each have one that is not, and by point $1$, this edge must connect to a vertex not in $C$.
Point $3$ says that there is no way to connect the other ends of the $7$ edges mentioned in point $2$ to the three vertices not in $C$. This is because, after you've connected $2$ to each of them, you still have one left, which will be the third edge connected to whatever vertex you connect it to.
Point $4$ has two parts. The first says that given $3$ vertices $C$ of $C$, at least $2$ of them are connected by a path of length $\le2$ in $C$. This is because if one of them is $3$ edges away from both of the others, then the others are neighbors because $C$ is a cycle of length $7$. The second half simply says that, since point $3$ tells us that there is a vertex (call it $a$) not in $C$ connected to $3$ vertices in $C$, and (by the first part of $4$) $2$ of these are connected by a path of length $2$ in $C$, the edges connecting $a$ to those $2$ vertices along with the path connecting them in $C$ is a cycle of length $4$. $\square$